当前位置:网站首页>Binary search and its variants of must know must know before interview

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 .

 Two points search 1

(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

 Two points search 2

(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

 Two points search 3

(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 .

 Two points search 4

(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.

 Two points search 6

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

Then return to .

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

 Two points search 2

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;
            }
        }
        // The element was not found , return  -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 .

 Binary search business trip

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

 Search insert location

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 to the insertion position 
        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

 Binary search variant 1

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 . Binary search lower boundary

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 .

 Left boundary 1

 Left boundary 2

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

 Binary search lower boundary 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

 Fuzzy boundary conditions

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 ?

 Binary search fuzzy boundary target value

We've got the above example , So let's take a look , When target = 0 when , How should the program be executed ?

 Fuzzy boundary target 0

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 !

If this article is of any help to you , Or can feel the intention of this article , Thank you so much for your kind comments , Looking at , Forward it , So I'll come back to life full of blood .

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 .

qrcode_for_gh_1f36d2ef6df9_258

版权声明
本文为[tan45du]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201208132321505s.html