704. Binary Search - Explanation

Description

You are given an array of distinct integers nums, sorted in ascending order, and an integer target.

Implement a function to search for target within nums. If it exists, then return its index, otherwise, return -1.

Your solution must run in $O(log n)$ time.

Example 1:

Input: nums = [-1,0,2,4,6,8], target = 4

Output: 3

Example 2:

Input: nums = [-1,0,2,4,6,8], target = 3

Output: -1

Constraints:

1 <= nums.length <= 10000.
-10000 < nums[i], target < 10000
All the integers in nums are unique.

Topics

Array Binary Search

Recommended Time & Space Complexity

You should aim for a solution with O(logn) time and O(1) space, where n is the size of the input array.

Hint 1

Can you find an algorithm that is useful when the array is sorted? Maybe other than linear seacrh.

Hint 2

The problem name is the name of the algorithm that we can use. We need to find a target value and if it does not exist in the array return -1. We have l and r as the boundaries of the segment of the array in which we are searching. Try building conditions to eliminate half of the search segment at each step. Maybe sorted nature of the array can be helpful.

Hint 3

We compare the target value with the mid of the segment. For example, consider the array [1, 2, 3, 4, 5] and target = 4. The mid value is 3, thus, on the next iteration we search to the right of mid. The remaining segment is [4,5]. Why?

Hint 4

Because the array is sorted, all elements to the left of mid (including 3) are guaranteed to be smaller than the target. Therefore, we can safely eliminate that half of the array from consideration, narrowing the search to the right half and repeat this search until we find the target.

Company Tags

Google6 Amazon4 Bloomberg4 Infosys4 Cognizant2 Meta2 Microsoft2 Oracle2 PureStorage2 TCS2 Yandex2

Prerequisites

Before attempting this problem, you should be comfortable with:

Arrays - Understanding how arrays are indexed and accessed
Sorted Arrays - Recognizing properties of sorted data that enable efficient searching
Recursion - Writing and understanding recursive functions with base cases
Time Complexity - Understanding O(log n) vs O(n) and why halving the search space is efficient

1. Recursive Binary Search

Intuition

Binary search works by repeatedly cutting the search space in half.
Instead of scanning the entire array, we check the middle element:

If it’s the target → return the index.
If the target is larger → search only in the right half.
If the target is smaller → search only in the left half.

The recursive version simply expresses this idea as a function that keeps calling itself on the appropriate half until the target is found or the range becomes invalid.

Algorithm

Define a recursive function that takes the current search range [l, r].
If l > r, the range is empty, return -1.
Compute the middle index m = (l + r) // 2.
Compare nums[m] with target:
- If equal, return m.
- If nums[m] < target, recursively search [m + 1, r].
- If nums[m] > target, recursively search [l, m - 1].
Start the recursion with the full range [0, n - 1].
Return the final result.

class Solution:
    def binary_search(self, l: int, r: int, nums: List[int], target: int) -> int:
        if l > r:
            return -1
        m = l + (r - l) // 2

        if nums[m] == target:
            return m
        if nums[m] < target:
            return self.binary_search(m + 1, r, nums, target)
        return self.binary_search(l, m - 1, nums, target)

    def search(self, nums: List[int], target: int) -> int:
        return self.binary_search(0, len(nums) - 1, nums, target)

class Solution {
public:
    int binary_search(int l, int r, vector<int>& nums, int target){
        if (l > r) return -1;
        int m = l + (r - l) / 2;

        if (nums[m] == target) return m;
        return ((nums[m] < target) ?
                binary_search(m + 1, r, nums, target) :
                binary_search(l, m - 1, nums, target));
    }

    int search(vector<int>& nums, int target) {
        return binary_search(0, nums.size() - 1, nums, target);
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number}
     */
    binary_search(l, r, nums, target) {
        if (l > r) return -1;
        let m = l + Math.floor((r - l) / 2);

        if (nums[m] === target) return m;
        return nums[m] < target
            ? this.binary_search(m + 1, r, nums, target)
            : this.binary_search(l, m - 1, nums, target);
    }

    search(nums, target) {
        return this.binary_search(0, nums.length - 1, nums, target);
    }
}

func binarySearch(l, r int, nums []int, target int) int {
    if l > r {
        return -1
    }
    m := l + (r-l)/2

    if nums[m] == target {
        return m
    }
    if nums[m] < target {
        return binarySearch(m+1, r, nums, target)
    }
    return binarySearch(l, m-1, nums, target)
}

func search(nums []int, target int) int {
    return binarySearch(0, len(nums)-1, nums, target)
}

class Solution {
    private fun binarySearch(l: Int, r: Int, nums: IntArray, target: Int): Int {
        if (l > r) {
            return -1
        }
        val m = l + (r - l) / 2

        return when {
            nums[m] == target -> m
            nums[m] < target -> binarySearch(m + 1, r, nums, target)
            else -> binarySearch(l, m - 1, nums, target)
        }
    }

    fun search(nums: IntArray, target: Int): Int {
        return binarySearch(0, nums.size - 1, nums, target)
    }
}

class Solution {
    func binarySearch(_ l: Int, _ r: Int, _ nums: [Int], _ target: Int) -> Int {
        if l > r {
            return -1
        }
        let m = l + (r - l) / 2

        if nums[m] == target {
            return m
        }
        if nums[m] < target {
            return binarySearch(m + 1, r, nums, target)
        }
        return binarySearch(l, m - 1, nums, target)
    }

    func search(_ nums: [Int], _ target: Int) -> Int {
        return binarySearch(0, nums.count - 1, nums, target)
    }
}

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(\log n)$

2. Iterative Binary Search

Intuition

Binary search checks the middle element of a sorted array and decides which half to discard.
Instead of using recursion, the iterative approach keeps shrinking the search range using a loop.
We adjust the left and right pointers until we either find the target or the pointers cross, meaning the target isn’t present.

Algorithm

Initialize two pointers:
- l = 0 (start of array)
- r = len(nums) - 1 (end of array)
While l <= r:
- Compute m = l + (r - l) // 2 (safe midpoint).
- If nums[m] == target, return m.
- If nums[m] < target, move search to the right half: update l = m + 1.
- If nums[m] > target, move search to the left half: update r = m - 1.
If the loop ends without finding the target, return -1.

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

        while l <= r:
            # (l + r) // 2 can lead to overflow
            m = l + ((r - l) // 2)

            if nums[m] > target:
                r = m - 1
            elif nums[m] < target:
                l = m + 1
            else:
                return m
        return -1

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

        while (l <= r) {
            int m = l + ((r - l) / 2);
            if (nums[m] > target) {
                r = m - 1;
            } else if (nums[m] < target) {
                l = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }
}

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number}
     */
    search(nums, target) {
        let l = 0;
        let r = nums.length - 1;

        while (l <= r) {
            const m = l + Math.floor((r - l) / 2);
            if (nums[m] > target) {
                r = m - 1;
            } else if (nums[m] < target) {
                l = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }
}

public class Solution {
    public int Search(int[] nums, int target) {
        int l = 0, r = nums.Length - 1;

        while (l <= r) {
            int m = l + ((r - l) / 2);
            if (nums[m] > target) {
                r = m - 1;
            } else if (nums[m] < target) {
                l = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }
}

func search(nums []int, target int) int {
    l, r := 0, len(nums)-1

    for l <= r {
        m := l + (r-l)/2

        if nums[m] > target {
            r = m - 1
        } else if nums[m] < target {
            l = m + 1
        } else {
            return m
        }
    }
    return -1
}

class Solution {
    fun search(nums: IntArray, target: Int): Int {
        var l = 0
        var r = nums.size - 1

        while (l <= r) {
            val m = l + (r - l) / 2

            when {
                nums[m] > target -> r = m - 1
                nums[m] < target -> l = m + 1
                else -> return m
            }
        }
        return -1
    }
}

class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        var l = 0, r = nums.count - 1

        while l <= r {
            // (l + r) // 2 can lead to overflow
            let m = l + (r - l) / 2

            if nums[m] > target {
                r = m - 1
            } else if nums[m] < target {
                l = m + 1
            } else {
                return m
            }
        }
        return -1
    }
}

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

3. Upper Bound

Intuition

Upper bound binary search finds the first index where a value greater than the target appears.
Once we know that position, the actual target—if it exists—must be right before it.
So instead of directly searching for the target, we search for the boundary where values stop being ≤ target.
Then we simply check whether the element just before that boundary is the target.

Algorithm

Set l = 0 and r = len(nums) (right is one past the last index).
While l < r:
- Compute midpoint m.
- If nums[m] > target, shrink the right side: r = m.
- Otherwise (nums[m] <= target), shrink the left side: l = m + 1.
After the loop:
- l is the upper bound: first index where nums[l] > target.
- So the potential location of the target is l - 1.
If l > 0 and nums[l - 1] == target, return l - 1.
Otherwise, return -1 (target not found).

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

        while l < r:
            m = l + ((r - l) // 2)
            if nums[m] > target:
                r = m
            elif nums[m] <= target:
                l = m + 1
        return l - 1 if (l and nums[l - 1] == target) else -1

public class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length;

        while (l < r) {
            int m = l + ((r - l) / 2);
            if (nums[m] > target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return (l > 0 && nums[l - 1] == target) ? l - 1 : -1;
    }
}

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size();

        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] > target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return (l > 0 && nums[l - 1] == target) ? l - 1 : -1;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number}
     */
    search(nums, target) {
        let l = 0,
            r = nums.length;

        while (l < r) {
            let m = l + Math.floor((r - l) / 2);
            if (nums[m] > target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l > 0 && nums[l - 1] === target ? l - 1 : -1;
    }
}

public class Solution {
    public int Search(int[] nums, int target) {
        int l = 0, r = nums.Length;

        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] > target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return (l > 0 && nums[l - 1] == target) ? l - 1 : -1;
    }
}

func search(nums []int, target int) int {
    l, r := 0, len(nums)

    for l < r {
        m := l + (r-l)/2
        if nums[m] > target {
            r = m
        } else {
            l = m + 1
        }
    }
    if l > 0 && nums[l-1] == target {
        return l - 1
    }
    return -1
}

class Solution {
    fun search(nums: IntArray, target: Int): Int {
        var l = 0
        var r = nums.size

        while (l < r) {
            val m = l + (r - l) / 2
            if (nums[m] > target) {
                r = m
            } else {
                l = m + 1
            }
        }
        return if (l > 0 && nums[l - 1] == target) l - 1 else -1
    }
}

class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        var l = 0, r = nums.count

        while l < r {
            let m = l + (r - l) / 2
            if nums[m] > target {
                r = m
            } else {
                l = m + 1
            }
        }
        return (l > 0 && nums[l - 1] == target) ? l - 1 : -1
    }
}

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

4. Lower Bound

Intuition

Lower bound binary search finds the first index where a value is greater than or equal to the target.
This means if the target exists in the array, this lower-bound index will point exactly to its first occurrence.
So instead of directly searching for equality, we search for the leftmost position where the target could appear, then verify it.

This approach is especially useful for sorted arrays because it avoids overshooting and naturally handles duplicates.

Algorithm

Initialize:
- l = 0
- r = len(nums) (right is one past the last index).
While l < r:
- Compute midpoint m.
- If nums[m] >= target, shrink the search to the left half: r = m.
- Otherwise (nums[m] < target), search in the right half: l = m + 1.
After the loop:
- l is the lower bound: first index where value >= target.
If l is within bounds and nums[l] == target, return l.
Otherwise, return -1 (the target is not in the array).

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

        while l < r:
            m = l + ((r - l) // 2)
            if nums[m] >= target:
                r = m
            elif nums[m] < target:
                l = m + 1
        return l if (l < len(nums) and nums[l] == target) else -1

public class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length;

        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] >= target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return (l < nums.length && nums[l] == target) ? l : -1;
    }
}

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size();

        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] >= target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return (l < nums.size() && nums[l] == target) ? l : -1;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number}
     */
    search(nums, target) {
        let l = 0,
            r = nums.length;

        while (l < r) {
            let m = l + Math.floor((r - l) / 2);
            if (nums[m] >= target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l < nums.length && nums[l] === target ? l : -1;
    }
}

public class Solution {
    public int Search(int[] nums, int target) {
        int l = 0, r = nums.Length;

        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] >= target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return (l < nums.Length && nums[l] == target) ? l : -1;
    }
}

func search(nums []int, target int) int {
    l, r := 0, len(nums)

    for l < r {
        m := l + (r-l)/2
        if nums[m] >= target {
            r = m
        } else {
            l = m + 1
        }
    }
    if l < len(nums) && nums[l] == target {
        return l
    }
    return -1
}

class Solution {
    fun search(nums: IntArray, target: Int): Int {
        var l = 0
        var r = nums.size

        while (l < r) {
            val m = l + (r - l) / 2
            if (nums[m] >= target) {
                r = m
            } else {
                l = m + 1
            }
        }
        return if (l < nums.size && nums[l] == target) l else -1
    }
}

class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        var l = 0, r = nums.count

        while l < r {
            let m = l + (r - l) / 2
            if nums[m] >= target {
                r = m
            } else {
                l = m + 1
            }
        }
        return (l < nums.count && nums[l] == target) ? l : -1
    }
}

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

5. Built-In Function

import bisect
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        index = bisect.bisect_left(nums, target)
        return index if index < len(nums) and nums[index] == target else -1

class Solution {
public:
    int search(vector<int>& nums, int target) {
        auto it = lower_bound(nums.begin(), nums.end(), target);
        return (it != nums.end() && *it == target) ? it - nums.begin() : -1;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number}
     */
    search(nums, target) {
        // There is no built in function for JS.
        return nums.indexOf(target);
    }
}

func search(nums []int, target int) int {
    index := sort.Search(len(nums), func(i int) bool { return nums[i] >= target })
    if index < len(nums) && nums[index] == target {
        return index
    }
    return -1
}

class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        let index = nums.partitioningIndex { $0 >= target }
        return (index < nums.count && nums[index] == target) ? index : -1
    }
}

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

Common Pitfalls

Integer Overflow When Calculating Mid

Using (l + r) / 2 can overflow when l and r are large. Use l + (r - l) / 2 instead to safely compute the midpoint.

# Wrong: can overflow in some languages
m = (l + r) // 2
# Correct: prevents overflow
m = l + (r - l) // 2

Infinite Loop Due to Wrong Pointer Update

Updating l = m instead of l = m + 1 (or r = m instead of r = m - 1 in some variants) can cause an infinite loop when l and r are adjacent.

Off-by-One Errors with Loop Condition

Using while l <= r vs while l < r changes the behavior significantly. Mixing these up with the wrong pointer updates causes bugs. Be consistent with your chosen template.

Not Checking if Target Was Actually Found

Binary search converges to a position, but that position might not contain the target. Always verify that nums[result] == target before returning the index.