What is binary search

Binary Search, also known as Binary Search, is a highly efficient Search method, provided that the data structure must be sorted first and the Search can be completed within the logarithmic time complexity of the data size. However, binary lookup requires linear tables to have random access (such as arrays), and also requires linear tables to be able to deduce the properties of the elements on both sides of the table from the characteristics of the elements in the middle, so as to reduce the size of the problem. Binary search problem is often tested in the interview questions, although its idea is very simple, but writing binary search algorithm is not an easy thing.

Tips: Data must be ordered, that is, in order

Don’t understand? That’s okay. Let me make it a little bit easier to understand.

Let’s start with an array:

let arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

If I want to find the index of the sixth number, 5, how do I find it? This is nonsense……

let target = 5;

for(let i = 0, len = arr.length; i < len; i++){

      if(arr[i] == target){

            return i;

      }

}

And then if we look at this code, let’s say that the length of the array is n, we have to find it n times in order n time. What if there’s a lot of data? 100, 1,000, 10,000; Or even 100,000 more. Does the time complexity go up linearly? This is where binary lookup comes in handy.

Binary search basic idea

Tips: Since the data is sorted, we can do this. (The index of the median here is mid)

1. Use two Pointers, one to the first number, left = 0, one to the last number, right = arr. Length – 1

2. Take the median and determine the size of the median arr[mid] and target

If the median value is greater than the target value, return mid. Because the array is ordered, it must be before the median, 0 to (mid-1), and what if it’s less than the target? Because the array is ordered, it must be after the median, mid+1 to the end of the array. So, if the target value is in the first half of the array, narrow the right boundary, right = mid-1. If the target value is in the lower half of the array, narrow the left margin, left = mid + 1.

4. Then enumerate the above three steps, the key is when to stop? When left = right, the search scope is already a number and can not be reduced any more. If you reduce the search scope by half, you can stop it.

let target = 5;
let left = 0
let right = arr.length - 1;
while(left <= right){
   let mid = Math.floor((right + left) / 2)
   if(arr[mid] === target){     // Find the target value
      return mid; 
   }else if(arr[mid] > target){ // If the value is larger than the target value, the number is in the first half
      right = mid - 1;
   }else{                       // If the value is smaller than the target value, it indicates that the number is in the back half, and Narrows the left margin
      left = mid + 1; }}Copy the code

According to the comparison between the target value and the median, the search scope can be reduced by half each time, so the time complexity is log N. If there is a large amount of data, the efficiency of this dichotomy is very high. Students can check it out for themselves.

Binary search advanced thinking

The left border

Now let’s change our array to something like this

let arr = [0, 1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9]

Or something like this

let arr = [0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9]

or

Let arr = [……….. this array is very long, the value inside is very large]

The question becomes how do you find the first 5 and the last 5? Is it possible to use the above method? Obviously not.



Train left boundary: 1 0 2 trips to the middle value: 8 train the right border of 3:17 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- train left border 4:9 trip to the middle value 5:13 trips to the right border of 6: 17 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - 13Copy the code

Obviously, passing the above test cannot meet the requirements, and each time you narrow the boundary, you only need to find one that meets the conditions and quit. So, can we modify it so that we can find the first one or the last one by shrinking the left and right sides of the boundary without exiting? The answer is yes. How do we modify the code? Take your time



Train left boundary: 1 0 2 trips to the middle value: 8 train the right border of 3:17 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- train left border 4:9 trip to the middle value 5:13 trips to the right border of 6: 17 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- train left border 4:9 trip to the middle value 5:13 trips to the right border of 6:17 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the fourth trip left margin: On September 5 intermediate values: train the right border of 6:13 17 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- train left border 4:9 trip to the middle value 5:13 trips to the right border of 6: 17 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 11Copy the code

The right boundary

Similarly, the right boundary is the same, you just have to shrink the left boundary



Let arr = [……….. this array is very long, the value inside is very large]

Let mid = left + (right-left) / 2 let mid = left + (right-left) / 2 However, normally left and right represent the array index value, and left is non-negative, so the possibility of right-left overflow is very small.

The following two ways are recommended

let mid = (left + right) >>> 1 ;
let mid = left + (right - left) / 2;Copy the code

We don’t have to bother, we can just write it this way, lock the interval at [left, right], and there’s going to be one that happens to be equal to the target, and one that happens to be different. Look directly at the code and comments.



Let’s optimize the code accordingly



conclusion

At this point, you have mastered the details and templates of dichotomy, and with a little practice you can become proficient. Actually, this is pretty basic, so you can optimize it by just saying if and else statements. Optimization as a schoolmate’s homework ~ hurry to practice ~

Here is an online template, in fact, is a sentence. Left plus right, no left, find right, find left, find right. Can you think about why?



Template explanation:

I couldn’t understand it at first. What good is this? Optimize the judgment conditions.

First of all, for the base notation and template above, the base notation is only suitable for finding one value, and the termination condition is right! = left, and the search interval is [left, right], and the loop is terminated when [2,3] or [3,2]. So you’re going to have to make a little bit more judgment when it equals, because there are too many judgments.

For template writing, the search interval is [left, right], left closed, right open.

Search the left boundary: Because it is left closed and right open, when mid is the target value, shrink the right boundary so that the target value is as close to the left as possible.

Search the right boundary: Because it is left closed and right open, when mid is the target value, shrink the left boundary so that the target value is as close to the right as possible.

For more details, please refer to leetcode-cn.com/explore/lea…