对旋转数组进行均等划分后,总有一边是有序的,如:
10 11 12 13 14 15 1 2 3
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; } };