将旋转点之后的数据整体放在数组之前：
上面说二分查询只是针对有序的数组，这又不是一个有序的数组，但是数组分成两部分有序的数组。
- 使用二分查找查看由 mid 分割出来的两部分 [l,mid] 和 [mid 1,r] 哪个部分是有序的，并根据有序的那个部分确定二分查找的左右边界
- 如果[l,m-1]是有序数组，并且 target 的大小在 [l,mid] 中，则将搜索目标缩小至[l,mid - 1],否则范围在 [mid 1，r] 中寻找。
- 如果[mid,r]是有序数组，并且 target 的大小在 [mid 1,r] 中，则将搜索目标缩小至[mid 1,r],否则在[l,mid - 1] 中寻找。
public int search(int[] nums, int target) {
int length = nums.length;
if (length == 0) {
return -1;
}
if (length == 1) {
return nums[0] == target ? 0 : -1;
}
int left = 0,right = length-1;
while (left <= right) {
int mid = left (right - left)/2;
if (nums[mid] == target) {
return mid;
}
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target < nums[mid]) {
right = mid -1;
} else {
left = mid 1;
}
} else {
if (nums[mid] < target && target <= nums[length - 1]) {
left = mid 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
69.x的平方根题目描述
求解平法根，也就是k² <= x，也就是求解 k 最大整数值。对 x 进行二分查找。
- 左边界是0，右边界是为x，每次二分查找到中间值 mid，mid 的平方的 x 的大小做对比。
- 如果 mid 的平方小于等于 x，赋值结果，并且左边界移动到 mid 1 的位置。
- 如果 mid 的平方大于x，将有边界移动到 mid - 1 的位置。
- 直达找到最优的解。
public int mySqrt(int x) {
if (x == 0 || x == 1) {
return x;
}
int left = 1;
int right = x;
int result = -1;
while (left <= right) {
int mid = left (right - left)/2;
if ((long)mid * mid > x) {
right = mid - 1;
} else {
result = mid;
left = mid 1;
}
}
return result;
}
153.寻找旋转排序数组中的最小值题目描述
