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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//The array is A, and what we want to search is target. int start = 0; int end = 0; while (start < end) { int mid = (start + end) / 2; if (A[mid] == target) return mid; if (A[mid] < target) start = mid + 1; else end = mid - 1; } return -1; |

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.