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