Binary Search

A binary search algorithm works by repeatedly dividing the sorted array in half until the desired element is found or until the entire array is exhausted.

Binary search appears simple, but implementing it correctly often involves subtle boundary conditions. For example:

• Should the loop be while (left < right) or while (left <= right)?
• Should we update right == middle, or right == middle -1?
• What happens when left == right?

The key to these confusions is the definition of the search interval .

Core Principle: Interval Definition

Binary search must preserve a strict invariant: at every iteration, the target must reside within a well-defined interval. Two standard interval definitions are:

• Left-closed, right-closed: [left, right]
• Left-closed, right-open: [left, right)

In each case, the loop condition, termination state, and how we update pointers must all align with the chosen definition.

Taking for example we are going to search 2 in the array [1, 2, 3, 4, 7, 9, 10].

I. Interval Definition: [left, right].

In this version, both left and right are valid candidate indices — the search space is inclusive on both ends.

1. Invariant Maintained:
   • target ∈ [left, right]
2. Initialization:
   • left = 0, right = nums.length - 1 — both inclusive.
3. Loop Condition:
   • while (left <= right)
4. When left == right:
   • the single element at that index is still valid and must be checked.
5. Pointer Update Rules:
   • If nums[middle] > target:
     • Eliminate the right half including middle, set right = middle - 1;
   • If nums[middle] < target:
     • Eliminate the left half including middle, set left = middle + 1;

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        // Define interval as [left, right]
        int right = nums.length - 1; 

        // Since [left, right] is inclusive, use <=
        while (left <= right) { 
            // Prevents overflow
            int middle = left + (right - left) / 2; 

            if (nums[middle] == target) {
                return middle;
            } else if (nums[middle] > target) {
                // Search in [left, middle - 1]
                right = middle - 1; 
            } else {
                // Search in [middle + 1, right]
                left = middle + 1; 
            }
        }

        return -1; // Target not found
    }
}

II. Interval Definition: [left, right).

In this version, left is inclusive and right is exclusive. The element at index right is never considered part of the search space.

1. Invariant Maintained:
   • target ∈ [left, right)
2. Initialization:
   • left = 0, right = nums.length — so that the last index (nums.length - 1) is included in [left, right)
3. Loop Condition:
   • while (left < right)
4. When left == right:
   • the loop must terminate, as this means the interval is empty.
5. Pointer Update Rules:
   • If nums[middle] > target:
     • Eliminate the right half including middle, set right = middle;
     • If we incorrectly set right = middle - 1 (as used in [left, right] intervals), we would violate the right-open invariant — it would no longer be valid to assume right is exclusive.
   • If nums[middle] < target:
     • Eliminate the left half including middle, set left = middle + 1;
     • If we incorrectly set left = middle — that would re-include a value already ruled out, potentially causing an infinite loop when left == right - 1.

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        // Define interval as [left, right)
        int right = nums.length; 

        // right is exclusive, so use '<'
        while (left < right) {   
            // Prevent integer overflow
            int middle = left + (right - left) / 2;

            if (nums[middle] == target) {
                return middle; 
            } else if (nums[middle] > target) {
                // Narrow to [left, middle)
                right = middle; 
            } else {
                // Narrow to [middle + 1, right)
                left = middle + 1; 
            }
        }

        return -1; // Target not found
    }
}