background

Today, Xiao Zheng, Xiao Ming and Xiao Hong are playing a guessing game, with Xiao Hong playing the banker. The rules of the game are that each contestant has three chances. If the contestant has not guessed the number after using up three chances, they will treat the dealer to a lollipop. If they guess correctly, the dealer will treat them to a candy bar. Eat a lollipop.

Now the game starts, please ask Xiaohong to write down a number on a sticky note. Xiao Hong wrote 97 on the post-it note in anticipation.

Xiao Ming: 50, right?

Xiaohong: No, it’s too small

Xiao Zheng: 75, is that okay?

Xiaohong: Haha, wrong, too small

Xiao Ming: 87, right?

Xiaohong: You are wrong again, it is too small

Xiao Zheng: 93, right?

Xiaohong: Almost, it’s too small

Xiao Ming: Is it 96?

Xiaohong: What a pity. You have no chance. Please eat a lollipop.

Xiao Zheng replied thoughtfully: 97

Xiaohong: Wow, you are great. Let’s go eat lollipops.

From the example above, we can extract a model. Given a set of ordered arrays, compare the target value with the value near the middle of the range each time. If it is too large, give the middle value to the left range and then find it from the middle value of the new range. If it is too small, give the middle value to The right range is searched from the middle value of the new range. If it is found, we return the index corresponding to its array subscript. If it is not found, we return -1. A search method like this is called "binary search".

Implement a binary search algorithm

There is a question about binary search. We will use this as an example to implement a binary search.

Question description

Given an n-element sorted (ascending) integer array nums and a target value, write a function to search nums and return the subscript if the target value exists, otherwise return -1.

Example 1:

Input: nums = [-1,0,3,5,9,12], = 9 Output: 4 Explanation: 9 appears in nums with subscript 4

Example 2:

Input: nums = [-1,0,3,5,9,12], = 2 Output: -1 Explanation: 2 does not exist in nums so -1 is returned

Example 3

Input: nums=[2, 5], =2

Output: 0,

Explanation: 2 appears in nums and has subscript 0

hint:

You can assume that all elements in nums are unique. n will be between [1, 10000]. Each element of nums will be between [-9999, 9999].

The tips here are very helpful for reviewing the question. The first sentence tells you to rest assured that these data are not repeated. You can rest assured to write in the simplest way. The second sentence tells you that only 10,000 numbers are enough to survive. , the amount of data is pretty good. The third sentence tells you that you don’t have to worry about the range of the integer type overflowing, and this is a signed integer type. So the tips are still helpful, although they may not be reflected in the code.

Ideas

Let’s first analyze what binary search does? It's nothing more than taking the middle one within a range and comparing the size with the target element. If it doesn't exactly equal the target element, I will continue to select one of the two segments and continue to chop it until the last element is left. So obviously we need a while loop to help us do such a thing. The second thing we have to think about is, what are the conditions for this while loop to be established? We can't create an endless cycle. When the left flag is less than or equal to the right flag, we continue to loop. It may be easy for everyone to understand here, so what is the situation? Let’s take an example from Example 3. When I want to find the number 5, left=mid=0, right=1 for the first time. At this time, we find that it is too small. Then if the equal sign is not taken, We just exited, so we added the equal sign here. When left=right=1 for the second time, we just found it. Then we think about the third thing, which half should I take? At this time, you need to determine the size of the middle one and the target one. If it is too big, I will subtract 1 from the middle one and assign it to right. If it is too small, then I will add 1 to the middle one and assign it to left. , and then recalculate the middle one and compare again. Okay, let's code one code together.

Code

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
  var left = 0;
  var right = nums.length - 1;
  var mid = left + Math.floor((right - left) / 2);
  while(left  nums[mid]) {
      left = mid + 1;
    } else if (target < nums[mid]) {
      right = mid - 1;
    } else if (target === nums[mid]) {
      return mid;
    }
    mid = left + Math.floor((right - left) / 2);
  }
  return -1;
};

Question: What is the time complexity of binary search?

Let’s talk about the answer first, O(logn). The rough process is, n(1/2)^k = 1. If we work backwards, k = log2n, the time complexity reflected on the computer is logn.

What scenarios are binary search applicable to?

The interview is for brushing people off (because it is easy to make mistakes), the amount of data is medium, and the data does not overflow the range. The most important thing is to perform a binary search on a set of sorted numbers.

Take our first example above. The ordinary search takes 97 times, but the binary search idea is used 6 times. Isn't this very delicious?

references

704.Binary search():