---

一、二分法是什么？

二分法通常又叫二分查找，一般用于查找一个有序数组中的某个值的位置或者给定的特定值的插入位置；
相比把整个数组遍历一次的O（n)复杂度，二分查找可以把复杂度降低到O（logn);
二分查找的基础概念在这里就不再赘述，本文主要记录二分法的基本情况使用和采用二分思路来求解的一些问题。

二、二分法在什么情况下使用

二分法一定是建立在元素有序的前提下的(或数据具有二段性）；所以看到题目中出现有序数组等词时，并且要求我们查找某个值或者给一个值求插入位置，或者判断其中是否存在某个值或者利用二分思路求最大最小值等；这些都可以使用二分法；

二分法需要注意的细节
二分法的思路很简单，无非就是每次根据中值判断，然后缩减区间到原来的一半；二分法最容易出错的地方在于边界和细节处理，大体逻辑并不难写出，我们往往死在细节处理上。

二分法的边界模板分为两种；
一种是左闭右闭的区间写法[left,right]： while(left<=right) left的改变为left=mid+1,right的改变为right=mid-1;
一种是左闭右开的区间写法[left,right) : while(left<right) left的改变为left=mid+1,right的改变为right=mid;
在二分查找的过程中，保持不变量；这也就是循环不变量。

下面来看具体的应用

三、实际应用

写法一：区间左闭右闭【left,right】

class Solution {
    public int searchInsert(int[] nums, int target) {
    	int len=nums.length;
    	int left=0,right=len-1;
    	while(left<=right) {
    		int mid=(left+right)/2;
    		if(nums[mid]<target) {
    			left=mid+1;
    		}
    		else {
    			right=mid-1;
    		}
    	}
    	return left;
    }
}

写法二：区间左闭右开【left，right）

class Solution {
    public int searchInsert(int[] nums, int target) {
    	int len=nums.length;
    	int left=0,right=len;//左闭右开所以right为len
    	while(left<right) {
    		int mid=(left+right)/2;
    		if(nums[mid]<target) {
    			left=mid+1;
    		}
    		else {
    			right=mid;
    		}
    	}
    	return right;

    }
}

单纯的二分查找是很简单的，我们再来看看利用二分思路的题目。

思路：
对于有序数组，可以使用二分查找的方法查找元素。

但是这道题中，数组本身不是有序的，进行旋转后只保证了数组的局部是有序的，这还能进行二分查找吗？答案是可以的。

可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。拿示例来看，我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分，其中左边 [4, 5, 6] 这个部分的数组是有序的，其他也是如此。

这启示我们可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid , r] 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出 target 在不在这个部分：

• 如果nums[mid]==targrt;返回mid;否则
• 如果 [l, mid - 1] 是有序数组，且 target 的大小满足 [[nums[l],nums[mid])，则我们应该将搜索范围缩小至 [l, mid - 1]，否则在 [mid + 1, r] 中寻找。
• 如果 [mid, r] 是有序数组，且 target 的大小满足 (nums[mid+1],nums[r]]，则我们应该将搜索范围缩小至 [mid + 1, r]，否则在 [l, mid - 1] 中寻找。

总而言之，就是中间值的左边或者右边一定有一边是有序的，那么我们就可以借助这个有序区间来判断目标target是否在这个区间内，这部分的代码也是容易写出的，例如判断中间值左边是不是有序的就是 if(nums[left]<=nums[mid]) ;注意这里的细节<=,因为判断到最后可能一个区间里只有一个元素，所以用<=。确认是否有序后就可以判断target是否在这个有序区间内了，而对于另外一边我们只要直接用else处理即可。

class Solution {
    public int search(int[] arr, int target) {
    	if(arr.length==0) return -1;
    	int left=0,right=arr.length-1;
    	while(left<=right) {
    		int mid=(left+right)/2;
    		if(arr[mid]==target) return mid;
    		if(arr[left]<=arr[mid]) {//左边有序
    			if(arr[left]<=target&&target<arr[mid])//target在有序区间内
    				right=mid-1;
    			else
    				left=mid+1;
    		}
    		else {                     //右边有序
    			if(arr[mid]<target&&target<=arr[right])
    				left=mid+1;
    			else
    				right=mid-1;
    		}
    	}
    	return -1;
    }
}

这题相比上面多了重复元素，所以我们固定先判断左边是否有序，如果遇到nums[start]==nums[mid],即重复元素，我们就start++,除去重复元素再继续判断，因为是重复元素，所以也不用担心会导致删去可能是target的值。

class Solution {
    public boolean search(int[] nums, int target) {
    	if(nums.length==0) return false;
    	int left=0,right=nums.length-1;
    	while(left<=right) {
    		int mid=(left+right)/2;
    		if(nums[mid]==target) return true;
    		if(nums[left]==nums[mid]) {
    			left++;
    			continue;//不能漏，不然会继续进行下面的判断
    		}
    		if(nums[left]<=nums[mid]) {
    			if(nums[left]<=target&&target<nums[mid])
    				right=mid-1;
    			else
    				left=mid+1;
    		}
    		else {
    			if(nums[mid]<target&&target<=nums[right])
    				left=mid+1;
    			else
    				right=mid-1;
    		}
    	}
    	return false;
    }
}

思路：
这个题和上面两个类似，中间值的左边或者右边必定有一边的有序的；而我们只需要借助一个有序的一边来帮助我们判断，如果不符合那我们要找的应该就是另外一边；其实这也就是二分的核心思想，借助 一定的条件来不断的使区间缩小减半。

本题我们应该判断右边是否是有序的，因为我们要找的是最小值，

• 如果右边有序，比如[4,5,6,7];那最小值只可能在[left,mid]中，所以right=mid
• 如果右边无序，我们可以看看比如【1，2，3，4，5，6，7】；必然是1被挪到了mid的右边才会出现右边无序也就是【4，5，6，7，1，2，3】或者之后再挪几位的情况；也就是如果右边无序，最小作者必定在右边区间，则left=mid+1
• 注意这里的left和right的每次变化，符合左闭右开的模板写法（虽然这里不是真正的左闭右开）

class Solution {
    public int findMin(int[] nums) {
    	int low=0,high=nums.length-1;
    	while(low<high) {
    		int mid=(low+high)/2;
    		if(nums[mid]<nums[high])
    			high=mid;
    		else
    			low=mid+1;
    	}
    	return nums[low];
    }
}

这里是同样的思路，只不过数组中出现了重复元素，所以我们和上面的题目一样在判断之前处理一下重复元素就好了

class Solution {
    public int findMin(int[] nums) {
    	int low=0,high=nums.length-1;
    	while(low<high) {
    		int mid=(low+high)/2;
    		if(nums[mid]==nums[high])
    			high--;
    		else if(nums[mid]<nums[high])//不能用if，否则high--后mid没更新就会再次判断
    			high=mid;
    		else
    			low=mid+1;
    	}
    	return nums[low];
    }
}