Skip to main content
CodePeetCodePeet
CodePeet 150

Binary Search

EASYProblemSolveExternal Links

Description

Given a sorted array of integers nums arranged in ascending order and an integer target, write a function that searches for target within nums. If the target value exists in the array, return its index. If it does not exist, return -1.

Your solution must achieve O(log n) runtime complexity, where n is the number of elements in the array.

Examples

Example 1

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

Output: 4

Explanation: The value 9 is located at index 4 of the array. Starting from index 0: -1, 0, 3, 5, 9 — we count five positions (indices 0 through 4), and the fifth position holds 9. Since the target exists in the array, we return its index.

Example 2

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

Output: -1

Explanation: The value 2 does not appear anywhere in the array. The elements jump from 0 (index 1) to 3 (index 2) with no 2 in between. Since the target is absent, we return -1.

Example 3

Input: nums = [5], target = 5

Output: 0

Explanation: The array contains only one element, 5, which matches the target. It sits at index 0, so we return 0. This is the simplest possible case — no searching is needed beyond one comparison.

Constraints

  • 1 ≤ nums.length ≤ 10^4
  • -10^4 < nums[i], target < 10^4
  • All the integers in nums are unique
  • nums is sorted in ascending order

Editorial

Brute Force

Intuition

Imagine you are looking for a specific book on a long shelf. The most straightforward approach is to start from one end and check each book one by one until you find the one you want. You need no special strategy — just patience and persistence.

This is exactly what linear search does: examine each element in the array from left to right, comparing it with the target. The moment we find a match, we return its index. If we reach the end without finding the target, we know it is not in the array and return -1.

Linear search works on any array, sorted or not. It does not take advantage of the sorted order — it treats every array the same way. This makes it simple but potentially wasteful when extra information (like sorted order) is available.

Step-by-Step Explanation

Let's trace through with nums = [-1, 0, 3, 5, 9, 12], target = 9:

Step 1: Begin scanning from the start. Set pointer i = 0.

Step 2: Check nums[0] = -1. Is -1 equal to 9? No. This element is too small. Move to the next element.

Step 3: Check nums[1] = 0. Is 0 equal to 9? No. Still not a match. Continue scanning rightward.

Step 4: Check nums[2] = 3. Is 3 equal to 9? No. Even though the array is sorted and 3 is less than 9, linear search does not use this information — it simply moves on to the next element.

Step 5: Check nums[3] = 5. Is 5 equal to 9? No. We have now checked 4 elements with no success.

Step 6: Check nums[4] = 9. Is 9 equal to 9? Yes! We found the target at index 4.

Step 7: Return index 4. It took 5 comparisons to find the element.

Linear Search — Scanning Every Element — Watch how linear search checks each element one by one from left to right until the target is found or the array is exhausted.

Algorithm

  1. Iterate through the array from index 0 to n - 1
  2. At each index i, compare nums[i] with the target
  3. If nums[i] equals the target, return i immediately
  4. If the loop completes without finding a match, return -1

Code

class Solution {
public:
    int search(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }
};
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        for i in range(len(nums)):
            if nums[i] == target:
                return i
        return -1
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;
    }
}

Complexity Analysis

Time Complexity: O(n)

In the worst case, we check every element in the array before finding the target (if it is at the last position) or confirming it is absent (if we scan the entire array). Each comparison is O(1), and we perform up to n comparisons, giving O(n) total time.

Space Complexity: O(1)

We use only a single loop variable and no additional data structures. The space used does not depend on the input size.

Why This Approach Is Not Efficient

Linear search scans every element from left to right, requiring up to n comparisons in the worst case. While O(n) may seem acceptable for n up to 10^4, the problem explicitly demands O(log n) runtime complexity. Linear search cannot meet this requirement.

More importantly, linear search completely ignores the fact that the array is sorted. It treats a sorted array the same as an unsorted one, which means it wastes the most valuable piece of information available.

Consider the waste: when linear search checks the middle element and finds it is smaller than the target, it has learned that the target must be further right. Yet it still moves only one step at a time. A smarter approach would use this comparison to eliminate an entire half of the array at once.

The key insight is that in a sorted array, a single comparison with any element tells us which half of the array the target could be in. If we always compare with the middle element, we cut the search space in half with every comparison, reducing the total work from O(n) to O(log n). For n = 10,000 elements, that is the difference between 10,000 comparisons and roughly 14.

Line chart comparing O(n) linear search vs O(log n) binary search growth rates as array size increases
Line chart comparing O(n) linear search vs O(log n) binary search growth rates as array size increases

Optimal Approach - Binary Search

Intuition

Now imagine that bookshelf is organized alphabetically. Instead of starting from one end, you go straight to the middle. If the book you want comes after the middle book alphabetically, you know it must be in the right half — so you completely ignore the left half. You then go to the middle of the right half and repeat. Each time you check the middle, you eliminate half of the remaining books.

This is the core idea behind binary search: by leveraging the sorted order of the array, we can discard half the search space with every single comparison.

We maintain two boundaries — low and high — that define the current search space. At each step, we compute the middle index and compare nums[mid] with the target:

  • If nums[mid] equals the target, we are done.
  • If nums[mid] is less than the target, the target must be in the right half, so we move low to mid + 1.
  • If nums[mid] is greater than the target, the target must be in the left half, so we move high to mid - 1.

We repeat until the boundaries cross (meaning the target is not in the array) or we find the target.

Step-by-Step Explanation

Let's trace through with nums = [-1, 0, 3, 5, 9, 12], target = 9:

Step 1: Initialize two pointers: low = 0, high = 5. Our search space includes all 6 elements.

Step 2: Compute the middle index: mid = (0 + 5) / 2 = 2. Look at nums[2] = 3.

Step 3: Compare 3 with target 9. Since 3 < 9, the target must be in the right half. All elements at indices 0 through 2 are too small to be the target.

Step 4: Update low = mid + 1 = 3. The search space narrows to indices 3 through 5, containing [5, 9, 12] — just 3 elements remain.

Step 5: Compute the new middle: mid = (3 + 5) / 2 = 4. Look at nums[4] = 9.

Step 6: Compare 9 with target 9. They match! The target is found at index 4.

Step 7: Return 4. Binary search found the answer in just 2 comparisons, versus 5 for linear search on the same input.

Binary Search — Halving the Search Space — Watch how binary search eliminates half the search space at each step by comparing the middle element with the target, reaching the answer in just 2 iterations.

Algorithm

  1. Initialize two pointers: low = 0 and high = n - 1
  2. While low ≤ high:
    a. Compute the middle index: mid = low + (high - low) / 2 (this avoids integer overflow compared to (low + high) / 2)
    b. If nums[mid] == target, return mid
    c. If nums[mid] < target, the target is in the right half — set low = mid + 1
    d. If nums[mid] > target, the target is in the left half — set high = mid - 1
  3. If the loop ends without finding the target, return -1

Code

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0, high = nums.size() - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
};
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        low, high = 0, len(nums) - 1
        while low <= high:
            mid = low + (high - low) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                low = mid + 1
            else:
                high = mid - 1
        return -1
class Solution {
    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}

Complexity Analysis

Time Complexity: O(log n)

At each iteration, the search space is halved. Starting from n elements, after one comparison we have n/2, then n/4, then n/8, and so on. The number of times we can halve n before reaching 1 is ⌊log₂(n)⌋. Therefore, binary search performs at most ⌊log₂(n)⌋ + 1 comparisons. For n = 10,000, this is roughly 14 comparisons — vastly fewer than the 10,000 needed by linear search.

Space Complexity: O(1)

We use only three integer variables (low, high, mid) regardless of the input size. No additional data structures are allocated, so space usage is constant.