二分法的宗旨，在于每次搜索的时候舍弃了解不在的那一半，最后将区间缩小并逼近解。不仅是全集有序可以使用，分段有序也可以使用。
二分法算法框架
int[] nums = {};
int target = 0;
int start = 0;
int end = nums.length - 1;
while(start < end){
int mid = (end - start)/2 + start;
if(target > nums[mid]){
start = mid + 1;
}else if (target < nums[mid]){
end = mid - 1;
}else{
break;
}
}
}
我们知道两个数的中位数，可以使用Δx/2 + x，也可以(x1+x2)/2；但是出于极端的考虑，x1+x2有可能出现Integer或者long越位，所以推荐使用Δx/2 + x。
33. Search in Rotated Sorted Array
给定一个有序数组的任意次右移结果，找出某个元素的位置，不存在返回-1。
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2])。
image.png
在确定分段有序的时候，如果target在此范围内，就缩小到此范围，否则就使用另外一半区间。
public static int search(int[] nums, int target) {
if(nums == null || nums.length == 0){
return -1;
}
int start = 0;
int end = nums.length-1;
while(start <= end){
int mid = start + (end - start) / 2;
if(nums[mid] == target){
return mid;
}
if(nums[start] <= nums[mid]){
if(target >= nums[start] && target < nums[mid]){
end = mid - 1;
}else {
start = mid + 1;
}
}else {
if(target > nums[mid] && target <= nums[end]){
start = mid + 1;
}else{
end = mid -1;
}
}
}
return -1;
}
81. Search in Rotated Sorted Array II
这是上一题有duplicate的升级。
image.png
public boolean search(int[] nums, int target) {
if(nums == null || nums.length == 0){
return false;
}
int start = 0;
int end = nums.length-1;
while(start<=end){
int mid = (end - start)/2 + start;
if(nums[mid] == target){
return true;
}
if(nums[end] < nums[mid]){
if(target >= nums[start] && target < nums[mid]){
end = mid - 1;
}else{
start = mid + 1;
}
}else if(nums[end] > nums[mid]){
if(target <= nums[end] && target > nums[mid]){
start = mid + 1;
}else{
end = mid - 1;
}
}else{
end --;
}
}
return false;
}
154. Find Minimum in Rotated Sorted Array II
在一个旋转数组中找出最小值。
2,2,2,0,1为例
（1）找到中间位置，中间位置[2]没有[1]大，则start区间前进到mid，此时start=2,end=4
（2）找到中间位置，中间位置[0]比[1]要小，则end缩短至mid，此时start=2,end=3
（3）结束，比较2，3位置取最小值
如果mid位置等于end位置，则end直接往前移动一个位置。
image.png
public int findMin(int[] nums) {
int start = 0;
int end = nums.length-1;
while(start < end-1){
int mid = (end - start) / 2 + start;
if(nums[mid] < nums[end]){
end = mid ;
}else if (nums[mid] > nums[end]){
start = mid ;
}else{
end --;
}
}
return Math.min(nums[start],nums[end]);
}
