1, What is dichotomy?

Dichotomy, also known as binary search, is generally used to find the position of a value in an ordered array or the insertion position of a given specific value;
Compared with the O (n) complexity of traversing the entire array once, binary search can reduce the complexity to o (logn);
The basic concept of bisection search will not be repeated here. This paper mainly records the basic situation of bisection method and some problems solved by bisection idea.

2, When is dichotomy used

Dichotomy must be based on the premise of element order; Therefore, when we see the words such as ordered array in the title, we are required to find a value or find the insertion position for a value, or judge whether there is a value, or use the dichotomy idea to find the maximum and minimum value, etc; These can be dichotomized;

Details of dichotomy
The idea of dichotomy is very simple. It is just to judge according to the median value each time, and then reduce the interval to half of the original; The most error prone part of dichotomy lies in boundary and detail processing. The general logic is not difficult to write. We often die in detail processing.

The boundary templates of dichotomy are divided into two types;
One is the interval writing method [left,right]: while (left < = right) the change of left is left = mid + 1, and the change of right is right=mid-1;
One is the interval writing method [left, right): while (left < right) the change of left is left = mid + 1, and the change of right is right=mid;
Keep invariants in the process of binary search; This is the loop invariant.

Let's look at specific applications

3, Practical application

Writing method 1: the interval is closed left and 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 right+1;
    }
}

Writing method 2: left, right

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

    }
}

Simple binary search is very simple. Let's take a look at the problem of using binary thinking.

Idea:
For ordered arrays, you can use the binary search method to find elements.

However, in this problem, the array itself is not orderly. After rotation, only the local parts of the array are orderly. Can this be used for binary search? The answer is yes.

It can be found that when we divide the array into left and right parts from the middle, some of the arrays must be orderly. Take an example. After we separate from the position of 6, the array becomes two parts [4, 5, 6] and [7, 0, 1, 2]. Among them, the array of the left part [4, 5, 6] is orderly, and so are others.

This enlightens us that we can check which part of [l, mid] and [mid, R] of the current mid divided by the split position is ordered during the conventional binary search, and determine how to change the upper and lower bounds of the binary search according to the ordered part, because we can judge whether the target is in this part according to the ordered part:

• If num [mid] = = targrt; Return mid; otherwise
• If [l, mid - 1] is an ordered array and the size of the target satisfies [[num [l], Num [mid]), we should narrow the search scope to [l, mid - 1], otherwise we should look in [mid + 1, r].
• If [mid, r] is an ordered array and the size of the target satisfies (Num [mid + 1], Num [R]], we should narrow the search scope to [mid + 1, r], otherwise we should look in [l, mid - 1].

In short, one side of the left or right side of the intermediate value must be ordered, so we can use this ordered interval to judge whether the target is within this interval, and this part of the code is also easy to write. For example, if (Num [left] < = num [mid]) is used to judge whether the left side of the intermediate value is ordered; Pay attention to the details here < =, because it is judged that there may be only one element in the last interval, so use < =. After confirming whether the target is in order, we can judge whether the target is in this order range. For the other side, we just need to use else directly.

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]) {//Left order
    			if(arr[left]<=target&&target<arr[mid])//target is in an ordered interval
    				right=mid-1;
    			else
    				left=mid+1;
    		}
    		else {                     //Right order
    			if(arr[mid]<target&&target<=arr[right])
    				left=mid+1;
    			else
    				right=mid-1;
    		}
    	}
    	return -1;
    }
}

There are more duplicate elements in this question than the above, so we should first judge whether the left side is orderly. If we encounter num [start] = = num [mid], that is, duplicate elements, we will start + +, remove the duplicate elements and then continue to judge. Because it is a duplicate element, we don't have to worry about deleting the value that may be 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;//Do not omit, or you will continue to make the following judgment
    		}
    		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;
    }
}

Idea:
This question is similar to the above two questions. There must be one side in order on the left or right of the middle value; And we only need to use an orderly side to help us judge. If it does not meet the requirements, we should be looking for the other side; In fact, this is the core idea of dichotomy, which constantly reduces the interval by half with the help of certain conditions.

In this question, we should judge whether the right side is orderly, because we are looking for the minimum value,

• If the right side is ordered, such as [4,5,6,7]; The minimum value can only be in [left,mid], so right=mid
• If the right side is disordered, we can take a look, such as [1, 2, 3, 4, 5, 6, 7]; It is only when 1 is moved to the right of mid that the disorder on the right will appear, that is, [4, 5, 6, 7, 1, 2, 3] or move several digits later; That is, if the right side is disordered, the minimum author must be in the right section, then left=mid+1
• Note that each change of left and right here conforms to the template writing method of closing left and opening right (although it is not true to close left and open right here)

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];
    }
}

Here is the same idea, except that there are duplicate elements in the array, so we'll deal with the duplicate elements before judgment as in the above topic

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 cannot be used, otherwise the mid will be judged again if it is not updated after high -
    			high=mid;
    		else
    			low=mid+1;
    	}
    	return nums[low];
    }
}