First published at: github.com/USTB-musion…

Writing in the front

Today, let’s talk about an ordered data algorithm that appears frequently in front-end interviews — “binary search”.

Here are some common interview questions:

  1. How to find the time complexity of binary search ❓
  2. How to achieve recursive and non-recursive binary search ❓
  3. If there is duplicate data in the array, how can I find the last location of the element ❓
  4. If there is duplicate data in array, how to find the first element location that is greater than or equal to the target value ❓

You can think about how to answer the above question 🤔 and then read the rest with the answer in mind.

1. How to calculate the time complexity of binary search ❓

Question: how in the array,13,19,21,37,56,64,75,80,88,92 [5], find out the value of an element (such as 21) position in the array.

The simplest and most crude method is to simply iterate through the array and return the index, but the downside of this method is that if you’re unlucky and the value you’re looking for is at the end of the array, you’ll have to iterate n times to find that value. Time complexity is O(n).

For such an ordered set of data, is there a more efficient way to use the binary search that is to be introduced next?

Binary search, also known as half search. Using the dichotomy idea, divide the data into two halves each time you search, and start looking from the middle value.

As shown in the figure above, low and high represent the two subscripts of the array, and mid represents the middle subscript of the array.

  • If the target value is larger than the median value, that is, between mid and high, change the value of low. Compare the median.

  • If the target value is less than the median value, that is, between low and mid, change the value of high. Compare the median.

The above is the binary search process, then how to calculate its time complexity ❓

Assuming that the array is of length N, then after one search it becomes length N /2, after another search it becomes length N /4, and so on, and in the worst case, n/2^k is empty and the search stops. So we have the following formula:

N * n/2 * n/4 * n/8 * n/2^kCopy the code

So this is a geometric sequence, n / 2 to the k = 1, k is the number of searches. K =log2n, so the time complexity is O(logn), which is a very efficient algorithm.

How to achieve recursive and non-recursive binary search ❓

Note ️ that the recursive and non-recursive versions here are for simple cases. “Simple” means that there are no repeating elements, which will be explained later

The recursive version

function binary_search(arr, key) { var low = 0, high = arr.length - 1; while(low <= high){ var mid = parseInt(low + (high - low) / 2); if(key === arr[mid]){ return mid; } else if (key > arr[mid]){ low = mid + 1; } else if (key < arr[mid]){ high = mid -1; } else { return -1; }}}; Var arr =,13,19,21,37,56,64,75,80,88,92 [5]; var result = binary_search(arr, 21); console.log(result);Copy the code

And remember, don’t write mid as low plus high over 2, because if low plus high is too high, it overflows. So if I write it as low plus high-low over 2, I won’t have this problem. It is also possible to use a bit operation to replace low+(high-low)/2 with low+(high-low) >>1.

The recursive version

Binary lookup can also be implemented recursively in addition to the circular method described above.

function binary_search(arr,low, high, key) { if (low > high){ return -1; } var mid = low + ((high - low) >> 1); if(arr[mid] == key){ return mid; }else if (arr[mid] > key){ high = mid - 1; return binary_search(arr, low, high, key); }else if (arr[mid] < key){ low = mid + 1; return binary_search(arr, low, high, key); }}; Var arr =,13,19,21,37,56,64,75,80,88,92 [5]; var result = binary_search(arr,0, 11, 21); console.log(result);Copy the code

3. If there is duplicate data in array, how to find the last location of the element ❓

And the above introduction of binary search ideas:

function binary_search(arr, key) { var low = 0, high = arr.length - 1; while (low <= high) { var mid = low + ((high - low) >> 1); if (arr[mid] > key) { high = mid - 1; } else if (arr[mid] < key) { low = mid + 1; } else { if ((mid == arr.length - 1) || (arr[mid + 1] ! = key)) return mid; else low = mid + 1; } } return -1; } var arr =,13,19,21,21,37,56,64,75,80,88,92 [5]; var result = binary_search(arr, 21); console.log(result);Copy the code

conclusion

The above is the core knowledge of binary search, as long as the master of the above core knowledge, binary search variant problem will be solved. Try this in the comments section:

If there is duplicate data in array, how to find the first element location that is greater than or equal to the target value ❓

Example:,13,19,21,21,21,37,56,64,75,80,88,92 [5], and find the exact location of the first element is greater than or equal to 21Copy the code

You can pay attention to my public account “Muchen classmates”, goose factory code farmers, usually record some trivial bits, technology, life, perception, grow together.