在转动过的有序数组中寻找目标值
在转动过的有序数组中寻找目标值
http://www.nowcoder.com/questionTerminal/7cd13986c79d4d3a8d928d490db5d707
对旋转数组进行均等划分后，总有一边是有序的，如：
10 11 12 13 14 15 1 2 310 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;
}
};刷遍天下无敌手 文章被收录于专栏
秋招刷题历程
