Binary Search

Master this topic with zero to advance depth.

Binary Search

Given a sorted array of integers nums and a target value target, return the index of target if it exists. Otherwise, return -1. You must write an algorithm with $O(\\log N)$ runtime complexity.

Easy

Examples

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
9 exists at index 4.

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
2 does not exist in the array.

Approach 1

Level I: Brute Force (Linear Scan)

Intuition

The most basic way to find a target is to check every element one by one. While simple, it fails to exploit the 'sorted' property of the input.

⏱ $O(N)$💾 $O(1)$

Detailed Dry Run

Step	Index	Value	Match?
1	0	-1	No
2	1	0	No
3	2	3	No
4	3	5	No
5	4	9	Yes (Return 4)

java

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;
    }
}

Approach 2

Level II: Recursive Binary Search

Intuition

Binary search naturally follows a 'Divide and Conquer' pattern. We check the middle, and then solve the same problem on a smaller subarray (either left or right half).

⏱ $O(\\log N)$💾 $O(\\log N)$ due to recursion stack depth.

Detailed Dry Run

Target: 9, Range: [0, 5]

mid = 2 (val 3). 3 < 9. Recurse right half [3, 5].
mid = 4 (val 9). 9 == 9. Return 4.

java

class Solution {
    public int search(int[] nums, int target) {
        return binarySearch(nums, target, 0, nums.length - 1);
    }
    private int binarySearch(int[] nums, int target, int l, int r) {
        if (l > r) return -1;
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) return binarySearch(nums, target, mid + 1, r);
        return binarySearch(nums, target, l, mid - 1);
    }
}

Approach 3

Level III: Optimal (Iterative Binary Search)

Intuition

Iterative binary search is the industry standard. It achieves the same $O(\\log N)$ time but uses $O(1)$ constant space by avoiding recursion. Key point: Always use mid = l + (r - l) / 2 to avoid integer overflow.

⏱ $O(\\log N)$💾 $O(1)$

Detailed Dry Run

Step	L	R	Mid	nums[Mid]	Decision
1	0	5	2	3	3 < 9 → L = 3
2	3	5	4	9	9 == 9 → Return 4

java

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

← Previous QuestionConvert Sorted List to BST

Next Question →Search Insert Position

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.