704. Binary Search - Leetcode Solution

LeetCode problem

Solution code

💡 Step-by-Step Thought Process

Brute Force

Understand the problem: Find the index of a target value in a sorted array, or return -1 if it doesn't exist.
Iterate through each index i from 0 to the length of the array minus 1.
Check if the element at index i equals the target.
If a match is found, return the index i.
If no match is found after the loop, return -1.

Code Solution (Brute Force)

# Brute Force Solution
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        for i in range(n):
            if nums[i] == target:
                return i
        return -1
        # Time: O(n)
        # Space: O(1)

#include <vector>
using namespace std;

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

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

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === target) {
            return i;
        }
    }
    return -1;
};

Why the Brute-Force Solution is Inefficient

The brute-force solution checks every element in the array sequentially, ignoring the fact that the array is sorted, leading to:

Time Complexity: O(n), where n is the length of the array, as it may need to check all elements.
Space Complexity: O(1), as only a constant amount of extra space is used.
Performance Issue: For large sorted arrays, a linear search is inefficient since the sorted property allows for faster search methods.

Optimal Solution

The optimal solution uses binary search to exploit the sorted array, achieving O(log n) time complexity:

Initialize two pointers, left to 0 and right to the array length minus 1.
While left is less than or equal to right, compute the middle index as the average of left and right.
If the middle element equals the target, return the middle index.
If the middle element is greater than the target, adjust right to middle - 1 to search the left half.
If the middle element is less than the target, adjust left to middle + 1 to search the right half.
If the target is not found, return -1.

Code Solution (Optimal)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            middle = (right + left) // 2

            if nums[middle] == target:
                return middle
            elif nums[middle] > target:
                right = middle - 1
            else:
                left = middle + 1

        return -1

# Time Complexity: O(log(n))
# Space Complexity: O(1)

#include <vector>
using namespace std;

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;

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

            if (nums[middle] == target) {
                return middle;
            } else if (nums[middle] > target) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }

        return -1;
    }
};

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

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

            if (nums[middle] == target) {
                return middle;
            } else if (nums[middle] > target) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }

        return -1;
    }
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const middle = Math.floor(left + (right - left) / 2);

        if (nums[middle] === target) {
            return middle;
        } else if (nums[middle] > target) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }

    return -1;
};

Detailed Explanation

Understanding the Problem: Binary Search

The “Binary Search” problem is one of the most fundamental and efficient search algorithms. Given a sorted array and a target value, your task is to determine whether the target exists in the array, and if so, return its index. If the target does not exist, return -1.

Example:

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4 (because nums[4] = 9)

Why This Problem Matters

Binary search is a cornerstone of algorithmic thinking. It's widely used because of its efficiency — reducing the time complexity from O(n) in a linear search to O(log n). Mastering binary search is essential for understanding other advanced algorithms like binary search trees, search-related dynamic programming, and range-based queries.

Optimal Approach: Binary Search on a Sorted Array

Binary search works by repeatedly dividing the search range in half. If the middle element is equal to the target, we return its index. Otherwise, we eliminate half of the remaining elements by comparing the middle value to the target.

Steps:

Initialize two pointers: left = 0 and right = nums.length - 1.
While left <= right:
- Compute the middle index: mid = Math.floor((left + right) / 2)
- If nums[mid] == target, return mid.
- If nums[mid] > target, move the search to the left: right = mid - 1.
- If nums[mid] < target, move the search to the right: left = mid + 1.
If the loop ends, the target is not in the array. Return -1.

Example Walkthrough

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

left = 0, right = 5 → mid = 2 → nums[2] = 3 → target > 3 → left = 3
left = 3, right = 5 → mid = 4 → nums[4] = 9 → match → return 4

Time and Space Complexity

Time Complexity: O(log n), because each iteration cuts the search space in half.
Space Complexity: O(1), as the algorithm only uses a fixed amount of memory.

Edge Cases to Consider

Empty array → return -1 immediately
Single-element array → check that element directly
Target not in array → return -1
Target at the first or last index → ensure boundaries are handled correctly

Conclusion

The “Binary Search” problem showcases the power of divide-and-conquer algorithms. It’s simple, elegant, and efficient — making it a critical concept for solving complex problems efficiently. Knowing when and how to use binary search is an essential tool in every programmer’s toolbox.

NEW!Need help landing software roles? 💡

AlgoMap.io