NeetCode 150: Binary Search

Table of contents

The Problem

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

The Approach

The goal is to implement the Binary Search algorithm, which relies on the constraint that the elements are sorted in increasing order. First we set two boundaries, max & min. Then, we take the element at the midpoint of these two boundaries, comparing them with target.

If the current value is greater than target, it can be assumed that target exists only between min & the current midpoint value. We then set the the max to this midpoint. Vice versa for the scenario where the current value is smaller than target.

The above then repeated until the min boundary is greater than the max (target does not exist in nums).

My Solution

class Solution {
    public int search(int[] nums, int target) {
        int minBound = 0;
        int maxBound = nums.length - 1;

        while (maxBound >= minBound) {
            int midIndex = (maxBound + minBound) / 2;

            if (nums[midIndex] == target) {
                return midIndex;

            // Move maxBound "backwards", skipping the current index (already considered).
            } else if (nums[midIndex] > target) {
                maxBound = midIndex - 1;

            // Move minBound "forwards", skipping the current index.
            } else {
                minBound = midIndex + 1;
            }
        }
        return -1;
    }
}

We first initialize the mininum and maxmimum boundaries, minBound & maxBound respectively, at the opposite ends of the array.

Until both pointers cross (checked using the while loop), get the midIndex by taking the average of minBound & maxBound.

There are 3 scenarios when comparing the current element to target:

• If nums[midIndex] == target: target found.
• If nums[midIndex] > target: The index of target only could exist “behind” midIndex. Set maxBound to midIndex - 1.
• If nums[midIndex] < target: The index of target only could exist “in front of” midIndex. Set minBound to midIndex + 1.

If the loop completes & no value is returned, means all values were considered and target does not exist in nums, returning -1.