To help make the upcoming tips less abstract, I’m going to start with a sample problem that I’ll refer to when needed: LeetCode problem 704, Binary Search. I chose binary search because it has a short implementation that uses only basic language features, but even experts have trouble getting it right.

In Problem 704, you are given an array of integers `nums`

sorted in ascending order, and an integer `target`

. You must implement a function that returns the array index of `target`

, or `-1`

if `nums`

does not contain `target`

.

When you need to search a sorted array, binary search should be the first approach that comes to mind. The idea is to start in the middle, check which half contains the target, and repeat the search in that half. Keep doing this until you find the target or you get down to one element that isn’t the target.

Here is an iterative implementation that will work with minor changes in any C-style language:

```
public int search(int[] nums, int target) {
int lo = 0;
int hi = nums.length-1;
while (lo <= hi) {
int mid = lo+(hi-lo)/2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] < target) {
lo = mid+1;
} else {
hi = mid-1;
}
}
return -1;
}
```

`lo`

and `hi`

are the endpoints of the section we’re currently searching, starting with the first and last elements of the array. `mid`

is the middle of the range, calculated in a way that avoids the overflow bug that infamously tripped up the experts. If the target is at position `mid`

, we’re done. If it isn’t at position `mid`

, it must be higher than `mid`

, lower than `mid`

, or not found in `nums`

. If we exit the loop without finding `target`

, that means it isn’t in the array.

The tricky part of this implementation, besides the overflow bug, is the loop condition. What is it about the behavior of `lo`

and `hi`

that guarantees that if we ever reach the point where `lo > hi`

, we know that the target is not found?

I won’t go into the mathematical argument here (consult Sedgewick or Knuth for details). But the intuition is that on each iteration of the `while`

loop, we either return `mid`

, increase `lo`

by 1, or decrease `hi`

by 1. There is no case where a loop iteration results in `lo`

decreasing, `hi`

increasing, or neither variable changing. The variables are always moving towards each other. Therefore, if we don’t find the target, `lo`

must eventually increase to or beyond the value of `hi`

, or `hi`

must eventually decrease to or below the value of `lo`

. This guarantees that the loop will terminate if `target`

is not found.

*This year, I’m publishing a series of tips for effective LeetCode practice. To read the tips in order, start with A Project for 2023*