在转动过的有序数组中寻找目标值

class Solution {
public:
    // 不要被“旋转”而迷惑，“有序”并不是二分查找的核心
    // 二分查找的核心是"通过界桩快速决定查找方向，大幅缩短查找空间"
    // 只要能快速确定界桩，就能使用二分查找
    // 充分利用有序数组能够快速获取边界值的特性
    // 利用这一特性可以快速确定目标值应处的区间
    int search(vector<int>& nums, int target) {
        if (nums.empty())
            return -1;
        int lo = 0, hi = nums.size() - 1;
        
        while (lo <= hi) {
            int mi = lo + ((hi - lo) >> 1);
            if (nums[mi] == target)
                return mi;
            
            // 只要在普通的二分查找判断语句中加一层 && 来确定目标值所在的区间，即可以同样O(logn)的复杂度查找
            if (nums[lo] <= nums[mi] && (nums[lo] <= target && target < nums[mi]))
                hi = mi - 1;
            else if (nums[mi] <= nums[hi] && !(nums[mi] < target && target <= nums[hi]))
                hi = mi - 1;
            else
                lo = mi + 1;
        }
        return -1;
    }
};

好喜欢暴力搜索啊。

• 先判断是否发生旋转，判断旋转的依据就是数组的第一个值大于最后一个值。
• 如果没有发生旋转，直接用二分查找
• 如果发生了旋转，找出旋转点，确定了两个有序的子数组，然后在有序的子数组中进行二分查找。while循环结束，begin对应的是最大值，end对应的是最小值。

public class Solution {
    public int search(int[] A, int target) {
        if(A == null || A.length == 0){
            return -1;
        }
        int begin = 0;
        int end = A.length - 1;
        if(A[begin] < A[end]){
            return binarysearch(A, begin, end, target);
        }else{
            while(A[begin] > A[end]){
                if(end - begin == 1){
                    break;
                }
                int mid = (begin + end)/2;
                if(A[mid] > A[begin]){
                    begin = mid;
                }else{
                    end = mid;
                }
            }

            if(target >= A[0]){
                return binarysearch(A, 0, begin, target);
            }else{
                return binarysearch(A, begin+1, A.length - 1, target);
            }
        }

    }

    public int binarysearch(int[] A, int begin, int end, int target){
        if(A == null || A.length == 0){
            return -1;
        }
        while(begin <= end){
            int mid = (begin + end)/2;
            if(A[mid] > target){
                end = mid - 1;
            }else if(A[mid] < target){
                begin = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
}

class Solution {
public:
    /**
     *       L     M     R
     *   |-------|---|-------|
     *   | 0 1 2 | 4 | 5 6 7 |
     *   | 7 0 1 | 2 | 4 5 6 |
     * T | 6 7 0 | 1 | 2 4 5 |
     *   | 5 6 7 | 0 | 1 2 4 |
     *   |-------|---|-------|
     *   | 4 5 6 | 7 | 0 1 2 |
     * B | 2 4 5 | 6 | 7 0 1 |
     *   | 1 2 4 | 5 | 6 7 0 |
     *   |-------|---|-------|
     */

    int search(int A[], int n, int target) {
        int lo = 0, hi = n - 1;
        while(lo <= hi) {
            int mid = (lo + hi) >> 1;
            if(A[mid] == target) return mid;
            
            if(A[mid] < A[hi] && A[mid] < target && target <= A[hi])
                lo = mid + 1;  // target在T区 且 在L+M区
            else if(A[mid] > A[hi] && !(A[lo] <= target && target < A[mid]))
                lo = mid + 1;  // target在B区 且 不在L+M区
            else 
                hi = mid - 1;
        }
        return -1;
    }
};

对旋转数组进行均等划分后，总有一边是有序的，如：

1. 10 11 12 13 14 15 1 2 3
2. 10 11 15 1 2 3 4 5 6 7 8

我们定位到有序的一边后，对比target与有序子数组的左右边界，就可以作出搜索左侧还是右侧的决策。

代码如下：

第16行必须是<=，不能是<，举例——从[3,1]中查找1

//
// Created by jt on 2020/9/3.
//
class Solution {
public:
    /**
     *
     * @param A int整型一维数组
     * @param n int A数组长度
     * @param target int整型
     * @return int整型
     */
    int search(int* A, int n, int target) {
        // write code here
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (A[mid] == target) return mid;
            if (A[mid] >= A[left]) {
                // 左侧有序(含A[mid])
                if (A[mid] > target && A[left] <= target)
                    right = mid - 1;
                else
                    left = mid + 1;
            } else {
                // 右侧有序(含A[mid])
                if (A[mid] < target && A[right] >= target)
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }
        return -1;
    }
};

class Solution {
public:
    // 二分查找
    int search(int A[], int n, int target)
    {
        int left = 0,middle,right = n-1;
        while(left <= right)
        {
           middle = (right+left)>>1;
           if(A[middle] == target)
                return middle;
           if(A[left] <= A[middle])  /// left side is sorted
           {
               if(A[left] <= target && target < A[middle])
                   right = middle-1;
               else
                   left = middle+1;
           }
           else                     /// right side is sorted
           {
               if(A[middle] < target && target <= A[right])
                    left = middle+1;
               else
                    right = middle-1;
           }
        }
        return -1;
    }
};

class Solution {
public:
    /**
     * 
     * @param A int整型一维数组 
     * @param n int A数组长度
     * @param target int整型 
     * @return int整型
     */
    int search(int* A, int n, int target) {
        // write code here
        int left=0;int right=n-1;
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(A[mid]==target)  return mid;
            if(A[mid]<=A[right])
            {
                if(target>A[mid]&&target<=A[right])  left=mid+1;
                else  right=mid-1;
            }
            else 
            {
                if(target<A[mid]&&target>=A[left])  right=mid-1;
                else  left=mid+1;
            }
        }
        if(A[left]==target)  return left;
        else  return -1;
    }
};

判断target在中间的左边还是右边。判断某边时，需判断是在左边有序还是右边有序（若存在）中。
class Solution {
public:
    /**
     * 
     * @param A int整型一维数组 
     * @param n int A数组长度
     * @param target int整型 
     * @return int整型
     */
    int search(int* A, int n, int target) {
        // write code here
        int left = 0, right = n;
        while(left < right) {
            int m = (left) + ((right-left)>>1);
            if(A[m] == target) return m;
            if(A[left] <= A[m] && !(A[left] <= target && target < A[m])){
                left = m+1;
            }
            else if(A[left] > A[m] && (A[m] < target && target <= A[right-1])) {
                left = m+1;
            }
            else 
                right = m;
            
        }
        return -1;
    }
}; 

方法一
class Solution {
public:
    int search(int A[], int n, int target) {
        map<int,int>m;
        if(target==A[0])
            return 0;
        for(int i=0;i<n;i++)
            m[A[i]]=i;
        return m[target]>0?m[target]:-1;
    }
};

方法二
class Solution {
public:
    int search(int A[], int n, int target) {
        for(int i=0;i<n;i++)
            if(target==A[i])
                return i;
        return -1;
    }
};

class Solution {
public:
    int search(int A[], int n, int target) {
		int l = 0,h = n-1;
		while(l <= h)
		{
			int mid = (l+h)/2;
			if(A[mid] == target)
				return mid;
			if(A[l] <= A[mid])
			{
				if(A[l] <= target && target <= A[mid])
					h = mid - 1;
				else
					l = mid + 1;
			}else{
				if(A[mid] <= target && target <= A[h])
					l = mid + 1;
				else
					h = mid - 1;
			}
		}
		return -1;
    }
};

public class Solution {
    public int search(int[] A, int target) {
		int position = 0;
		for (int i = 1; i < A.length; i ++) {
			if(A[i] < A[i - 1]) position = i - 1;
		}
		int search1 = binarySearch(A, 0, position, target);
		int search2 = binarySearch(A, position + 1, A.length - 1, target);
		if(search1 == - 1 && search2 == - 1) return - 1;
		return search1 == - 1 ? search2 : search1;
	}
	public int binarySearch(int[] arr, int low, int high, int target) {
		while (low <= high) {
			int mid = (low + high) / 2;
			if(arr[mid] < target) low = mid + 1;
			else if(arr[mid] > target) high = mid - 1;
			else return mid;
		}
		return - 1;
	}
}

//题意：经过一次旋转的有序数组中，找到target数，并返回其位置
//使用二分查找,先找出有序数组分界点，如果target大于第一个数，则在左半边二分查找，反之在右边二分查找。
//分界点即数组最小点，亦可二分查找left，right逐步确定分界点(若是重复数组，只能乖乖顺序查找分界点)
public class Solution {
    public int search(int[] A, int target) {
        int left=0;
        int right=A.length-1;
        if(left==right){
            if(A[0]==target)
                return 0;
            else
                return -1;
        }
        int mid;
        while(left<right-1){//为了寻找分界点
            mid=(right-left)/2+left;// 直接使用(high + low) / 2 可能导致溢出
            if(A[mid]>A[left]){
                left=mid;
            }
            if(A[mid]<A[right]){
                right=mid;
            }            
        }
        int min=right;//得出分界点
        if(A[0]<=target){//在(第一点到分界点)左半部分二分查找
            left=0;
            right=min-1;
            while(left<=right){
                mid=(right-left)/2+left;
                if(A[mid]==target){
                    return mid;
                }
                else if(A[mid]>target){
                    right=mid-1;
                }
                else{
                    left=mid+1;
                }
            }
        }
        if(A[A.length-1]>=target){//在(分界点到最后一点)右半部分二分查找
            left=min;
            right=A.length-1;
            while(left<=right){
                mid=(right-left)/2+left;
                if(A[mid]==target){
                    return mid;
                }
                else if(A[mid]>target){
                    right=mid-1;
                }
                else{
                    left=mid+1;
                }
            }
        }           
        return -1;
    }
}

public class Solution {
    public int search(int[] a, int target) {
        int len=a.length;
        if(len==0){
            return -1;
        }
        int low=0;
        int high=len-1;
        int mid=0;
        while(low<=high){
            mid=(low+high)/2;
            if(a[mid]==target){
                return mid;
            }
            //判断是正常的排序顺序
            if(a[low]<=a[high]){
                if(a[mid]>target){
                    high=mid-1;
                }else{
                    low=mid+1;
                }
            }
            //否则就是存在旋转的排序
            else{
                //判断左边有序（low直到mid 有序,a[low]是左边最小值，a[mid]是左边序列的最大值）
                if(a[low]<=a[mid]){
                    //如果target介于a[low]与a[mid]之间，就在左边找
                   if(target>=a[low]&&target<a[mid]){
                       high=mid-1;
                   }else{
                       low=mid+1;
                   }
                }
                //判断右边有序，（mid直到high有序）
                else{
                    //如果target介于a[mid]与a[high]之间，就在右边找
                    if(target>a[mid]&&target<=a[high]){
                        low=mid+1;
                    }else{
                        high=mid-1;
                    }
                }
            }
        }
        return -1;
    }
}