旋转数组是要么全部有序，要么两个部分有序。每次做二分查找，每次mid和最右边值作比较，会出现两种情况。
第一种情况是 nums[pivot] < nums[high]，如上图所示，此时最小值应该在 piot 的左侧，height 缩进到 pivot 的位置。
第二种情况是 nums[piot] > num[height], 如上图所示，此时最小值应该在 piot 的右侧，low 缩进到 piot 的位置。
class Solution {
public int findMin(int[] nums) {
int low = 0,height = nums.length-1;
while (low < height) {
int mid = low (height - low)/2;
if (nums[mid] < nums[height]) {
height = mid;
} else {
low = mid 1;
}
}
return nums[low];
}
}
367.有效的完全平方数题目描述
- 判断一个数是否是完全平方数，需要找到他的开根数。
- 使用二分法查找，如果 num < 2 返回true，因为 0 和都是完全平方数。
- 2 为 left，num 为 right，通过 left (right - left)/2 找到中间值
- 如果 mid² = num，返回true。
- 如果 mid² < num,left = mid 1。
- 如果 mid² > num ,right = mid - 1。
public boolean isPerfectSquare(int num) {
if (num <= 2) {
return true;
}
int left = 2,right = num/2,y;
long square;
while (left <= right) {
y = left (right - left)/2;
square =(long) y * y;
if (square == num) {
return true;
}else if (square > num) {
right = y - 1;
}else {
left = y 1;
}
}
return false;
}
总结
搜索有序的数组的元素，使用二分查找是一个高效率的查询方法。定位左右两侧最大值和最小值，找到中间值。然后通过目标值和中间值做对比，缩小搜索范围，直到搜索找到符合条件数据。
有时候无需全部有序，两部分有序也是可以通过二分查找找到符合要求的数据。
