Binary Search

NeetCode: Binary Search · LeetCode: 704. Binary Search · Difficulty: Easy

Given a sorted array of distinct integers nums and a target, return the index of target, or -1 if it is not present. The solution must run in O(log n).

Example

Text

Input:  nums = [-1, 0, 2, 4, 6, 8], target = 4    Output: 3
Input:  nums = [-1, 0, 2, 4, 6, 8], target = 3    Output: -1

Brute force: linear scan

LeetCode's Java signature is int search(int[] nums, int target).

Java

public class Main {
    static class Solution {
        public int search(int[] nums, int target) {
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == target) {
                    return i;
                }
            }
            return -1;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.search(new int[] {-1, 0, 2, 4, 6, 8}, 4));
        System.out.println(s.search(new int[] {-1, 0, 2, 4, 6, 8}, 3));
    }
}

Output

3
-1

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

Optimal: binary search

Keep the target inside a half-open range [lo, hi). Look at the middle: if it equals the target, return its index; if it is smaller than the target, the answer lies to the right; otherwise it lies to the left. Each step halves the range.

Java

public class Main {
    static class Solution {
        public int search(int[] nums, int target) {
            int lo = 0, hi = nums.length;
            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;
                }
            }
            return -1;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.search(new int[] {-1, 0, 2, 4, 6, 8}, 4));
        System.out.println(s.search(new int[] {-1, 0, 2, 4, 6, 8}, 3));
        System.out.println(s.search(new int[] {}, 3));
    }
}

Output

3
-1
-1

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

lo + (hi - lo) / 2 avoids the overflow that (lo + hi) / 2 can cause: int addition wraps silently, so for indexes near Integer.MAX_VALUE the sum can become negative. The half-open range means hi = mid never moves hi below 0. The standard library has the same search as Arrays.binarySearch(int[], int). When the key is missing it returns -(insertion point) - 1, not -1, so a method that must return -1 has to convert that result.