Binary Search with Invariants: Easy and Clear Approach
Tags: algorithms, beginners, javascript, binarysearch
Published: 2023-09-22 16:03:04

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.

```javascript
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.

```javascript
  - - - + + + +
[ 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:

```
[ - - - - - + + ]
[ - - - - - - - ]
[ + + + + + + + ]
```
{% details 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.{% enddetails %}
{% details 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.{% enddetails %}

### 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.

```javascript
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.

```javascript
  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:
```javascript
    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:

```javascript
// ...
      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.

```javascript
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.

```javascript
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

```javascript
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`

**Solution**

Write the predicate and let the binary search find the first non-negative number.

```
const predicate = (num) => num >= 0

  - + + + +
[-3 0 1 5 7]

 + + +
[4 4 4]

  -  -  -
[-9 -8 -1]
```
Then handle the result in the solution.

```javascript
function solution(arr) {
  const predicate = (num) => num >= 0
  const lastNonNegative = binarySearch(predicate, arr)

  return lastNonNegative - 1
}
```

## 🎉 Conclusion

Implement binary search function by these steps:

- write a **predicate**
- choose **invariants** for left and right pointers (you know which are the best)
- **rely on** invariants to **init** the pointers
- **rely on** invariants to write the **loop exit** condition
- find the **middle**
- find the predicate value at the middle and change one of the pointers
- return one of the pointers from the function

After a bit of practice binary search will become a reliable tool in your hands.

_Happy coding!_