Binary search algorithm variant

Why I want to write this article?
The 3 variants of binary search algorithm confuses me frequently? Why do I need to set right = size or right = size -1? Why is the termination condition is left < right or left ≤ right?

So in this article I want to explore a little bit about the reason behind 3 main variant of binary search algorithm.

  1. the classic binary search algorithm

In this algorithm, we want to find exactly the index of the target in the sorted saerch array.

The (right + 1) return value means what is the index of the target that should be inserted into the array. Or we can return -1 if we didn’t find the target.

The termination condition of this binary search variant is (left > right).

2. The second one is quite useful.

we cannot just return the mid index once we find the index that satisfy our target or that is equal to our target.

What happen in this method is that there may be multiple elements that satisfy our condition, and we want to find the element that is closest to our target.

So we set our termination condition to (left < right). And we may not just immediately return the mid index once we get the index that satifies our condition.

the element the mid points to is still under consideration. Here is the code.

For example.

Bad version. Suppose we have a project and every time we have an project update we will have to do a test on the project. Given a project test status array, we want to find out the earliest version at which the project didn’t pass the test.

For example, given test status array [1, 0, 0, 0, 0, 0, 0].

Starting from index 0. the first version that fails the test is index 4.

So begin with left = 0, right = 6. The first mid index is (6 + 0) / 2 = 3. And a[mid] == 0. But we couldn’t just return this index since it is not the earliest version that fails the test. We still need too move left until stop at the point where (left index == right index).

Here is the code

Why this algorithm is correct?

The second example is that given multiple files where each file contains sorted keys and the files are arranged in sorted order and they have non-overlapping key ranges.

For example, given 3 files in sorted order. a1 = [1 , 3, 5, 11], a2 = [13, 15, 27, 30], a3 = [35, 38, 39, 59]

if we want to find out

multiple files that may contain the search key.

--

--

master of SYSU, do research on computer system software

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store