Using an invariant to determine the boundary conditions in a typical binary search problem

Question

I am trying to solve the typical binary search question on LeetCode.com:

Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1. So for [-1,0,3,5,9,12], target = 9; the output is 4.

As per a solution, the invariant used is:

target is within nums[lo ... hi]

However, given this invariant, I am unsure how to determine the boundary conditions:

class Solution {
    public int search(int[] nums, int target) {
        // Loop invariant: target is within nums[lo ... hi] 
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mi = lo + (hi - lo) / 2;
            if (nums[mi] == target) {
                return mi;
            } else if (nums[mi] > target) {
                hi = mi - 1;
            } else {
                lo = mi + 1;
            }
        }
        
        return -1;
    }
}

How did the invariant help us determine:

a. lo<=hi instead of just lo<hi in the while loop condition?
b. hi=mi-1 instead of hi=mi in the else clause?
c. lo=mi+1 instead of lo=mi in the else clause?

Personally, when I solved the question myself, I used the invariant as a[lo]<=target<=a[hi] based on this SO answer, but I still had questions analogous to the three above. Sure, I could take a few examples to understand what to do, but I am specifically focusing on using invariants to determine what to do.

I am new to using invariants in binary search, so would appreciate any kind of help. Thanks!

Not answering your question. It's my personal opinion, but it's much simpler to work in terms of half-intervals `[lo, hi)` (i.e. `lo <= index(target) < hi`). When you compare `nums[mi]` with target, if `target < nums[mi]`, then `hi := mi` (since `index(target) < mi`), else `lo := mi` (since `mi <+ index(target)`). Half-intervals are also useful in other settings (such as segment trees, range queries, etc.) — , Jul 16 '20 at 03:44
@Dmitry in your example, if `target < nums[mi]` then why `hi := mi`? Why not `hi := mi-1`? — , Jul 16 '20 at 03:48
Because our invariant is `index(target) < hi`. You know that `index(target) < mi` (you've just determined that `target < nums[mi]`), and you don't know anything about `index(target)` vs `mi-1` (e.g. it can be the case that `target = nums[mi-1]`). Therefore, we set `hi := mi`. — , Jul 16 '20 at 03:50
@Dmitry also one follow up - in your example, what would the conditional expression within the while loop (the termination condition) be? `lo<=hi` or `lo — , Jul 16 '20 at 04:39
`while (hi - lo > 1)`. You want to repeat the loop while there are at least two elements remaining in the interval, and the number of elements is `hi - lo`. I guess this `1` is the price to pay for getting rid of `+-1` everywhere else:) — , Jul 16 '20 at 04:46

Using an invariant to determine the boundary conditions in a typical binary search problem

0 Answers0