Binary search and its variants of must know must know before interview

2020-12-08 13:23:44 tan45du

Need more algorithmic details , You can search by wechat [ Yuan Chu's algorithmic cottage ]

What I bring you today is a summary of binary search and its variants , We must see the end , Full of heart , I don't say much nonsense , Let the director cut the scene to Yuanji restaurant for us ！

In Yuanji restaurant ....

Shopkeeper ： Shopkeeper , You've come back from your purchase , yo ！ The fish you bought today is quite big ！

Yuan Chu ： That is , I bought this from our riverside today , I've been shopping in the vegetable market before , The rich people there , Guess how much I bought today .

Shopkeeper ： The fish before ,30 A copper plate, a piece of , Today I guess 26 Copper coin .

Yuan Chu ： Expensive .

Shopkeeper ： It's still expensive ！ So I guess 20 Copper coin ！

Yuan Chu ： It's still expensive .

Shopkeeper ：15 Copper coin .

Yuan Chu ： It's cheaper

Shopkeeper ：18 Copper coin

Yuan Chu ： Congratulations on your guesses

The above example uses our binary search idea , If you've played a similar game , That binary search must be easy to understand , Let's conquer the next two ！

Binary search is also called binary search （Binary Search）, It is a search algorithm to find a specific element in an ordered array . We can see from the definition that , The premise of binary search is that the array must be ordered , What needs to be noted here is , Our input doesn't have to be an array , It can also be the beginning and ending position of an interval in the array

Through the above definition of binary search , We know the function and requirement of binary search algorithm , So what is the specific implementation process of the algorithm ？

Let's use an example to help us understand . We need to be in nums Array , Query element 8 The index of

int[ ]  nums = {1,3,4,5,6,8,12,14,16}; target = 8

（1） We need to define two pointers to the head and tail of the array , This is what we look up in the entire array , When we're in the array

When a query is made in a certain interval , You can enter an array , The starting position , Stop location to query . （2） find mid, The index is mid =（left + right）/ 2, But writing like this may overflow , So we need to improve it and write it as

mid = left +（right - left）/ 2 perhaps left + ((right - left ) >> 1) The two functions are the same , It's all about finding the middle of two pointers

Inter index , It's faster to use bit operations . So the mid = 0 + (8-0) / 2 = 4 （3） Now our mid = 4,nums[mid] = 6 < target, So we need to move our left The pointer , Give Way left = mid + 1, Next time you can do it in the new left and right Search the target value in the interval , The figure below shows before and after the move （4） We need to be in left and right Between mid value ,mid = 5 + （8 - 5）/ 2 = 6 And then nums[mid] And target Continue to compare , And then decide to move next time left The pointer is still right The pointer , See the picture below （5） We found that nums[mid] > target, We need to move our right The pointer , be right = mid - 1; Then after moving our left and right It will overlap , Here is a key point for us. We need to pay attention to , This will be described in detail later . （6） We need to be in left and right Continue to calculate between mid value , be mid = 5 +（5 - 5）/ 2 = 5 , See the picture below , At this point we are going to nums[mid] and target Compare , Then we find that the two values are equal , return mid that will do , If it's not equal, jump out of the loop , return -1. The execution process of binary search is as follows

1. From an ordered array or interval , Take out the elements in the middle , Compare it to our target value , Judge whether it is equal , If equal

2. If nums[mid] and target It's not equal , On the other hand nums[mid] and target Value to compare the size , By comparing the results, it is decided that it is from mid

The left or right part of the search continues . If target > nums[mid] Then the right half interval continues to search , namely left = mid + 1; if

target < nums[mid] Then continue to search in the left half of the interval , namely right = mid -1;

Moving graph analysis Let's take a look at the binary search code , You can think about it if The condition of the statement , There's no shorthand for each .

public static int binarySearch(int[] nums,int target,int left, int right) {
// Here we need to pay attention to , The loop condition
while (left <= right) {
// Here we need to pay attention to , Calculation mid
int mid = left + ((right - left) >> 1);
if (nums[mid] == target) {
return mid;
}else if (nums[mid] < target) {
// Here we need to pay attention to , Move the left pointer
left  = mid + 1;
}else if (nums[mid] > target) {
// Here we need to pay attention to , Move the right pointer
right = mid - 1;
}
}
return -1;
}

Binary search ideas and code has been understood , So let's take a look at the error prone aspects of implementation

1. Calculation mid when , Out of commission （left + right ）/ 2, Otherwise, it may lead to overflow

2.while (left < = right) { } Notice that in brackets left <= right , instead of left < right , Let's go back to the example , If we set the condition to left < right When we get to the last step , Is our left and right When overlapping , It will jump out of the loop , return -1, The element does not exist in the interval , But it's not like that , our left and right This point is to our target element , But at this time left = right Out of the loop

3.left = mid + 1,right = mid - 1 instead of left = mid and right = mid. Let's think about this situation , See the picture below , When our target Element is 16 when , And then we just left = 7 ,right = 8,mid = left + (right - left) = 7 + (8-7) = 7, Then if you set left = mid Words , Then it goes into a dead cycle ,mid The value has always been 7 . Let's take a look at the recursive writing of binary search

public static int binarySearch(int[] nums,int target,int left, int right) {

if (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target) {
// Find success
return  mid;
}else if (nums[mid] > target) {
// New range , Left half range
return binarySearch(nums,target,left,mid-1);
}else if (nums[mid] < target) {
// New range , Right half range
return binarySearch(nums,target,mid+1,right);
}
}
// There is no return -1
return -1;
}

Example ：

Title Description

Given a sort array and a target value , Find the target value in the array , And return its index . If the target value does not exist in the array , Return to where it will be inserted in sequence .

You can assume that there are no duplicate elements in the array .

Example 1:

Input : [1,3,5,6], 5
Output : 2

Example 2:

Input : [1,3,5,6], 2
Output : 1

Example 3:

Input : [1,3,5,6], 7
Output : 4

Example 4:

Input : [1,3,5,6], 0
Output : 0

title

This question is exactly the same as our binary search , It's just a little rewriting , That is to change our return value to left, The specific implementation process is shown in the figure below class Solution {
public int searchInsert(int[] nums, int target) {

int left = 0, right = nums.length-1;
// Pay attention to the circulation conditions
while (left <= right) {
// seek mid
int mid = left + ((right - left ) >> 1);
// The query is successful
if (target == nums[mid]) {
return mid;
// The right range
} else if (nums[mid] < target) {
left = mid + 1;
// Left interval
} else if (nums[mid] > target) {
right = mid - 1;
}
}
return left;
}
}

The above shows how to use binary search to find the index position of a specific value in an array or interval . But we didn't have duplicate values in the array just now , Check and return , So let's think about the following At this point, our array contains multiple 5 , We check whether it contains 5 It's easy to find out , But we want to get the first 5 and the last one 5 How to achieve the position of ？ Oh ！ We can use traversal , When you find the first 5 when , We set up a pointer to locate , And then to the last one 5 When to return to , So we can get the first and last five ？ Because the theme of this article is binary search , Can we use binary search to achieve ？ Of course you can .

Title Description

Given an array of integers in ascending order nums, And a target value target. Find the start and end position of the given target value in the array .

If the target value does not exist in the array target, return [-1, -1].

Example 1：

Input ：nums = [5,7,7,8,8,10], target = 8
Output ：[3,4]

Example 2：

Input ：nums = [5,7,7,8,8,10], target = 6
Output ：[-1,-1]

Example 3：

Input ：nums = [], target = 0
Output ：[-1,-1]

title

The topic is easy to understand , We said above how to use traversal to solve this problem , But the purpose of this topic is to let us use binary search , Let's analyze... One by one , First find the lower boundary of the target element , So how do we find the lower boundary of the target element ？

Let's focus on the analysis of the code in the binary search

if (nums[mid] == target) {
return mid;
}else if (nums[mid] < target) {
// Here we need to pay attention to , Move the left pointer
left  = mid + 1;
}else if (nums[mid] > target) {
// Here we need to pay attention to , Move the right pointer
right = mid - 1;
}

We just need to modify it in this code , Let's dissect the code again ,nums[mid] == target When you return to ,nums[mid] < target Then move the left pointer , Search in the right range , nums[mid] > target Then move the right pointer , Search in the left range .

So let's think about it , If our nums[mid] = target , But we're not sure mid Whether it is the left boundary of the target number , So we can't go back to the subscript at this point . For example, in the following case . here mid = 4 ,nums[mid] = 5, But at this time mid It's not the first 5, So we need to keep looking for , Because we're looking for

It's the lower boundary of numbers , So we need to be able to mid Continue to look for the left range of the value of 5 , So what should we do ？ We just need to

target <= nums[mid] when , Give Way right = mid - 1 that will do , So that we can continue in mid Continue to look for 5 . It's not that it's a little winding , Let's describe it through the following set of pictures .  In fact, the principle is very simple , That is, we combine less than and equal together , When target <= nums[mid] when , We all move the right pointer , That is to say right = mid -1, Another thing to note is , When we calculate the lower boundary, the final return value is left , When the graph above ends the loop ,left = 3,right = 2, return left Just in time for our lower boundary . Let's take a look at the specific implementation process of finding the lower boundary .

Moving graph analysis Calculate the lower boundary code

int lowerBound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
// Here we need to pay attention to , Calculation mid
int mid = left + ((right - left) >> 1);
if (target <= nums[mid]) {
// When the target value is less than or equal to nums[mid] when , Continue to search in the left range , Find the first number
right = mid - 1;

}else if (target > nums[mid]) {
// The target value is greater than nums[mid] when , Then continue to search in the right interval , Find the first number equal to the target value
left = mid + 1;

}
}
return left;
}

The condition of calculating the upper boundary is opposite to that of the upper boundary ,

When calculating the lower boundary , When target <= nums[mid] when ,right = mid -1;target > nums[mid] when ,left = mid + 1;

On the boundary , When target < nums[mid] when ,right = mid -1; target >= nums[mid] when left = mid + 1; It's just the opposite of the condition when we calculate the lower boundary , return right.

Calculate the upper boundary code

int upperBound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
// seek mid
int mid = left + ((right - left) >> 1);
// Moving the left pointer
if (target >= nums[mid]) {
left = mid + 1;
// Moving the right pointer
}else if (target < nums[mid]) {
right = mid - 1;
}

}
return left;
}

Title complete code

class Solution {
public int[] searchRange (int[] nums, int target) {
int upper = upperBound(nums,target);
int low = lowerBound(nums,target);
// There is no situation
if (upper < low) {
return new int[]{-1,-1};
}
return new int[]{low,upper};
}
// Calculate the lower boundary
int lowerBound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
// Here we need to pay attention to , Calculation mid
int mid = left + ((right - left) >> 1);
if (target <= nums[mid]) {
// When the target value is less than or equal to nums[mid] when , Continue to search in the left range , Find the first number
right = mid - 1;

}else if (target > nums[mid]) {
// The target value is greater than nums[mid] when , Then continue to search in the right interval , Find the first number equal to the target value
left = mid + 1;

}
}
return left;
}
// Calculate the upper boundary
int upperBound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (target >= nums[mid]) {
left = mid + 1;
}else if (target < nums[mid]) {
right = mid - 1;
}
}
return right;
}
}

We're in the variants above , Describes how to find the upper and lower bounds of the target element in the array , Then let's look at a new variety , How to find the index of the first number greater than or the last less than the target element from an array or interval , example nums = {1,3,5,5,6,6,8,9,11} We want to find the first one greater than 5 The index of the element , Then we need to go back 4 , because 5 The back of it is 6, first 6 The index of is 4, If you want to find the last one less than 6 The elements of , Then we will return to 3 , because 6 In front of is 5 the last one 5 The index of is 3. Well, we have learned the subject , Let's take a look at how to find the first number greater than the target element in an array or interval .

Find the first number that is greater than the target element , There are probably the following situations 1. The array contains the target element , Find the first element behind him

2. The target element is not in the array , Some elements in the array are larger than it , At this point, we need to return the first element that is larger than it

3. The target element is not in the array , And all the elements in the array are larger than it , Then we can return the first element of the array

4. The target element is not in the array , And all the elements in the array are smaller than it , So we don't find , return -1 that will do .

Now that we've analyzed everything , Then this topic is not difficult for us , Let's describe the implementation process of the case

nums = {1,3,5,5,6,6,8,9,11} target = 7

In the example above , We need to find the first one greater than 7 Number of numbers , So how does our program work ？ We've got the above example , So let's take a look , When target = 0 when , How should the program be executed ？ OK! At this point, we will be able to give this variety a complete and clear , Now let's take a look at the program code , It's also very simple .

public static int lowBoundnum(int[] nums,int target,int left, int right) {

while (left <= right) {
// Find the intermediate value
int mid = left + ((right - left) >> 1);
// If it is greater than the target value
if (nums[mid] > target) {
// return  mid
if (mid == 0 || nums[mid-1] <= target) {
return mid;
}
else{
right = mid -1;
}

} else if (nums[mid] <= target){
left = mid + 1;
}
}
// All elements are smaller than the target element
return -1;
}

From the example above, we should be able to fully understand the variant , Let's move on to the following situation , That's how to find the last element less than the target number . Or the example above

nums = {1,3,5,5,6,6,8,9,11} target = 7

Find the last element less than the target number , For example, our target number is 7 , At this time, the number in front of him is 6, the last one 6 The index of is 5, At this point we return to 5 that will do , If the target number element is 12, So our last element is 11, Still less than the target number , So we're going back to 8, that will do . This variety is actually the opposite of the above one , It's up there , This can be done , Let's take a look at the code .

public static int upperBoundnum(int[] nums,int target,int left, int right) {

while (left <= right) {

int mid = left + ((right - left) >> 1);
// Less than the target
if (nums[mid] < target) {
// See if it's the last one in the current range , If the current is less than , More than one in the back , Return the current value
if (mid == right || nums[mid+1] >= target) {
return mid;
}
else{
left = mid + 1;
}

} else if (nums[mid] >= target){
right = mid - 1;
}
}
// No information has been found
return -1;
}

Ah, it says why there are so many , It's too long for everyone to watch , Let's put the rest in the next chapter , I'll see you next time ！

I'm chef yuan , A young man who loves to use dynamic graphic algorithms , A programmer who loves cooking , A little brother who wants to improve with you . https://chowdera.com/2020/12/20201208132321505s.html