Course4all

Binary Search

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Binary Search.

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(logN)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

StepIndexValueMatch?
10-1No
210No
323No
435No
549Yes (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]
  1. mid = 2 (val 3). 3 < 9. Recurse right half [3, 5].
  2. 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(logN)O(\\log N) time but uses O(1)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

StepLRMidnums[Mid]Decision
105233 < 9 → L = 3
235499 == 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;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionConvert Sorted List to BST
Next Question →Search Insert Position