Binary Search with Invariants: Easy and Clear Approach

neemkashu — Fri, 22 Sep 2023 16:03:04 +0000

Struggling with Binary Search? While the algorithm’s core concept is simple, implementing it without errors can be challenging. This is a guide to a debugging-free approach.

The core idea is to use predicates and invariants, which we’ll explore in detail.

NOTE: The article assumes that you are familiar with the idea of binary search. The aim is to improve your implementation skills.

💡 A couple of concepts

Invariant: some relation that will not change during the entire algorithm
Binary predicate: a function that returns boolean and is used for the search

📘 Binary Search Blueprint

The code is in JavaScript, but it looks almost the same in other popular languages, if you can pass a function as an argument. Also, you don’t have to worry about array index out-of-bounds errors: they won’t occur.

function binarySearch(predicate, arr) {
// we will replace '?' with correct code
  let l = ? // init left pointer
  let r = ? // init right pointer

  while( ? ) { // the end of the search
    let m = ? // middle pointer

    if (predicate(arr[m])) {
      ? // adjust pointers for a predicate true value
    } else {
      ? // and for the false value
    }
  }
  // return some number at the end
}

EVERYTHING in this prototype can be written without trial and error, without “oh, should it be +1 or -1” or rounding problems.

❓ Problem Statement

Let’s solve the following task

Given an array of integers, find the index of the first odd number in the array. All even numbers in the array are positioned to the left of the odd numbers.
Example: [2 6 4 5 9 1 1] Answer: 3
Example: [4 4 4] Answer: -1 (the index is not found)
Example: [3 7 5] Answer: 0

We’ll fill the blueprint’s gaps in the order of reasoning.

➡️Solution Step-by-Step ️➡️

Predicate ⚖️

We will write a function that changes from false to true at the border where the answer is located. Let’s use the following markers:

false as minus, -
true as plus, +

The predicate indicates we are to the left or to the right of the desired value.

  - - - + + + +
[ 2 6 4 5 9 1 1 ]

const predicate = (num) => num % 2 !== 0

predicate(5) === true
predicate(4) === false

Also, be sure that the predicate value changes at most once amoung the array values. Consider the possible predicate values for an arbitrary array:

[ - - - - - + + ]
[ - - - - - - - ]
[ + + + + + + + ]

Note 1: Find the last even number

You may want to choose a predicate that changes from true to false at some index, for example, if the task is to find the last even number. But you don’t have to: just choose what to return either l or r, as we’ll see later.

Note 2: Why bother with a predicate?

That makes the implementation independent of the specific problem or task. Find a few other examples of a predicate in the Examples section of the article.

Invariants 🔒

You need to choose statements about the left and right boundaries (l and r) that you will keep true during the entire algorithm. Let’s say these statements are:

l points to minus
only minuses are to the left of l
r points to plus
only pluses are to the right of r

In markdown illustration

l points to minuses only
  l     l
[ - - - - + + + + + ]

r points to pluses only
          r       r
[ - - - - + + + + + ]

Initial values 🌱

Let’s introduce a small convention. Let the predicate give a minus to the left of the array, and a plus to the right of the array. These checks will never be run in the code, but they will help to immediately place l and r

- - -               + + +
     [2 6 4 5 9 1 1]

So, place l and r to satisfy the invariants:

l points to “index” –1: we are sure that only minuses are to the left of index 0
r points to the right of the last index: the only known plus + at the initial state

- - -               + + +
     [2 6 4 5 9 1 1]
    l               r

Thus, the initial values are ready.

function binarySearch(predicate, arr) {

  let l = -1
  let r = arr.length

// the rest of the code
}

Loop test condition 🔄

The invariant gives a clue when to exit the loop. Illustrate the closest possible positions of l and r still satisfing the invariant.

l rightmost position

        l
[ - - - - + + + + + ] 
          r

r leftmost position

That’s it! End the loop when l and r are neighbors.

  while(l + 1 < r) {
    // code
  }

Predicate returns true ✅

We somehow calculated the middle m (about it later) and perform a check predicate(arr[m]). Consider the result which equals plus + , or true

- - -       m        + + +
     [      +       ]
    l                r

The target is somewhere between - and + so we will change the right pointer. Keep the invariant true: r points to plus + and only pluses are to the right.

Code update:

    if (predicate(arr[m])) {
      r = m
    }

Predicate returns false ❌

If the result of predicate(arr[m]) equals minus - , or false

- - -       m        + + +
     [      -       ]
    l                r

we will change the left pointer. The invariant: l points to minus and only minuses are to the left of l

- - -       m        + + +
     [- - - -       ]
            l        r

Code update:

// ...
      else {
      l = m
    }

What is `m` equal to? ➗

m is the middle between l and r but we have to round it up or down.

m = Math.floor((l + r) / 2)

           vs

m = Math.ceil((l + r) / 2)

Here comes the reason why our invariant is the best: the rounding does not matter. Consider such a situation: l и r are one iteration from the end of the loop. Despite of rounding, m points right between l and r so the next iteration ends the loop.

- - -         m          + + +      - - -         m        + + +
     [- - - - - + + + + ]       --->     [- - - - - + + + ]
            l   r                                 l r

- - -         m          + + +      - - -         m        + + +
     [- - - - + + + + + ]       --->     [- - - - + + + + ]
            l   r                               l r

Also, you automatically avoid the problem of an infinite loop.

🚀 Binary Search Code

The loop ends when l points to the last minus and r points to the first plus. The task is to find the first odd number so it is preferable to return r in our case.

function binarySearch(predicate, arr) {

  let l = -1
  let r = arr.length

  while(l + 1 < r) {
    let m = Math.floor((l + r) / 2)

    if (predicate(arr[m])) {
      r = m
    } else {
      l = m
    }
  }
  return r
}

Edge Cases and Problem Solution ⚠️

Remember the second test case of the task

Example: [4 4 4] Answer: -1 (the index is not found)

In this case, our binary search returns 3, and that’s intentional. Do not include task details into binary search code, just handle the results in the solution.

function solution(arr) {

  const predicate = (num) => num % 2 !== 0
  const firstOdd = binarySearch(predicate, arr)

  return firstOdd < arr.length ? firstOdd : -1
}

Next, let’s explore why we don't get the out-of-bounds error. You access the array’s elements only through index m. The following relations ensure that m is always greater than l and is less than r. Thus, m never equals -1 or an array length

m = Math.floor((l + r) / 2)
l + 1 < r

Examine how m changes during the search in this array.

Example: [4 4 4 6 8 8]

m = 2
-     m       +
 [4 4 4 6 8 8]
l             r

m = 4
- - - -   m   +
 [4 4 4 6 8 8]
      l       r

m = 5
- - - - - - m +
 [4 4 4 6 8 8]
          l   r

end of the loop
- - - - - - - +
 [4 4 4 6 8 8]
            l r

You can obtain a similar result when considering [1 3 5 7 9]: the minimum value of m is 0 just before the end of the search.

📝 Examples

Task 1

An array of integers is sorted in a non-decreasing order. Find the index of an arbitrary target integer. If the array includes several numbers equal to the target return the index of the first one.

Example: 9, [-1 0 1 5 7] Answer: -1 (the index is not found)
Example: 2, [4 4 4] Answer: -1 (the index is not found)
Example: 8, [-3 5 8 8 8 9] Answer: 2

Solution

Firstly, write the predicate: check that it returns only pluses, only minuses or changes once at the edge

const predicate = (num) => num >= target

Target: 9
  - - - - -
[-1 0 1 5 7]

Target: 2
 + + +
[4 4 4]

Target: 8
  - - + + + +
[-3 5 8 8 8 9]

Then, apply the binary search as a ready function and handle the results of the search

function solution(arr, target) {

  const predicate = (num) => num >= target
// index of greater or equal to target
  const geTarget = binarySearch(predicate, arr)

  if (geTarget >= arr.length) return -1
  return arr[geTarget] !== target ? -1 : geTarget
}

Task 2

Given an array of integers sorted in a non-decreasing order find the index of the last negative number.
Example: [-3 0 1 5 7] Answer: 0
Example: [4 4 4] Answer: -1 (the index is not found)
Example: [-9 -8 -1] Answer: 2