Binary Search

Given a sorted array of distinct integers, return the index of a target value, or -1 if absent.

EasyMust DoBinary SearchLeetCode

Why solve this?

It's the exact template every other binary-search problem in this course builds on.

Pattern recognition

A sorted array with a single target to locate is the textbook binary-search case — establish the loop invariant here before touching harder variants.

Prerequisites

Arrays

Hints

A linear scan works but is O(n) — the array being sorted should let you do better.
Keep `lo`/`hi` pointers and repeatedly halve the search space by comparing the middle element to the target.
Decide up front whether `hi` is inclusive or exclusive, and stay consistent.

Approach

Maintain an inclusive range `[lo, hi]`. While `lo <= hi`, compute `mid = lo + (hi - lo) / 2` to avoid overflow. If `nums[mid] == target`, return `mid`. If `nums[mid] < target`, the target must be to the right, so `lo = mid + 1`; otherwise `hi = mid - 1`. If the loop ends without a match, the target isn't present.

Java solution

Solution.java

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

Time: O(log n)Space: O(1)