Binary Search: Stop point

There are a lot of problems related to binary search. For example, Search for a Range, Search Insert Position on Leetcode. In these problems, sometimes we are not required to find a exact number, but to find the position of a number that is just larger than it, or find the first instance of the target, or find a correct position that the target can be inserted to.

Here is a implementation of binary search that can help you find the target. If the target is not exist, you can easily get the positions of the element that is just smaller and larger than the target.

This implementation is good. Why? Firstly, it can output the position of target if target exists in the array correctly. Secondly, what if the target is not in this array? You can modify the code to make it output the value of start and end. And at that time, start is the position that at this position the element is just larger than the target. And end is the position, at which the element is just smaller than the target.

It’s really helpful to decide the insert position of a given target. For instance, the problem “Search Insert Position” can be solved by replace the last line of this code by “return start”. Because in this problem, if you can’t find the target in the array, the position it need to insert is the position of the element which the smallest one among the elements that are larger than target.

 

  • There is a bug in “(start + end) / 2”, because it could overflow for big numbers. Change it to “start + (end – start)/2”.

    • decoet

      Yes. Your way is the best. Thank you.