Crack the Backend

Problem Statement

Given a sorted (non-decreasing) array nums and an integer target, return the index of target if it is in nums, otherwise return -1. The array is sorted in ascending order and has no duplicates (in the basic version).

O(log n) runtime is required; a linear scan would be O(n).
The search space is reduced by half each step by comparing target with the middle element.

Key Observations

In a sorted array, we can compare target with the middle element. If they are equal, we found the index. If target is less than the middle, the target (if present) must be in the left half; if greater, in the right half. So we narrow the search space to one half and repeat.
Use mid = left + (right - left) / 2 to avoid overflow. The loop condition left <= right ensures we check the last remaining element; when left > right, the search space is empty and we return -1.
Each iteration halves the search space, so total steps are O(log n).

Approach

High-level: Maintain a search range [left, right]. While left <= right, compute mid; if nums[mid] == target return mid. If nums[mid] < target, search the right half (left = mid + 1); else search the left half (right = mid - 1). If the loop exits, return -1.

Steps:

left = 0, right = nums.length - 1.
While left <= right: mid = left + (right - left) / 2. If nums[mid] == target, return mid. If nums[mid] < target, set left = mid + 1; else set right = mid - 1.
Return -1.

Implementation

Java

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            return mid;
        }

        if (nums[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }

    return -1;
}

Test Cases

Example 1

Input

nums = [-1,0,3,5,9,12], target = 9

Expected

4

Explanation

9 is at index 4.

Complexity Analysis

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

Follow-ups

Find leftmost/rightmost index of target (lower_bound/upper_bound).