#704

Easy

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Binary Search

Solve the Binary Search problem by finding the index of a target value in a sorted array with O(log n) complexity.

Problem Statement

Given a sorted array of integers, nums, and a target integer, target, implement a function to search for the target value in the array. If the target exists, return its index; otherwise, return -1.

The problem requires the solution to operate in O(log n) time complexity, which is achievable using a binary search technique. The array is sorted in ascending order and contains unique integers, which simplifies the search process.

Examples

Example 1

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

Output: 4

9 exists in nums and its index is 4

Example 2

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

Output: -1

2 does not exist in nums so return -1

Constraints

1 <= nums.length <= 104
-104 < nums[i], target < 104
All the integers in nums are unique.
nums is sorted in ascending order.

Solution Approach

Binary Search Algorithm

Start by initializing two pointers, left at the beginning of the array and right at the end. In each iteration, calculate the middle index, mid, and compare nums[mid] with the target. If nums[mid] is equal to the target, return mid. If the target is smaller than nums[mid], adjust the right pointer to mid - 1. If the target is larger, adjust the left pointer to mid + 1. This process continues until the target is found or the search space is exhausted.

Edge Case Handling

Ensure to handle cases where the target is not in the array. This is done by checking the left pointer against the right pointer. If left exceeds right, it means the target is not present in the array, and you should return -1.

Optimizing for Logarithmic Complexity

By halving the search space at each step, binary search achieves logarithmic time complexity, O(log n). This makes it significantly faster than linear search methods, especially for large arrays.

Complexity Analysis

Metric	Value
Time	O(\log n)
Space	O(1)

The time complexity of binary search is O(log n), as the search space is halved with each iteration. The space complexity is O(1) because no extra space is used except for the two pointers, left and right.

What Interviewers Usually Probe

Can the candidate efficiently explain how binary search works and its time complexity?
Does the candidate implement the binary search algorithm correctly without unnecessary computations?
Does the candidate handle edge cases, such as when the target is not present, effectively?

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the search space boundaries; incorrect pointer updates may lead to infinite loops or missing the correct index.
Not properly handling the case when the target is not found, leading to incorrect return values.
Overcomplicating the solution by adding unnecessary checks or conditions that don't affect the binary search logic.

Follow-up variants

Search for the target value in a descending sorted array.
Find the first occurrence of the target if there are duplicates.
Implement a binary search that finds the closest value to the target when it’s not present.

FAQ

What is the time complexity of Binary Search?

The time complexity of Binary Search is O(log n), as the search space is halved with each iteration.

Can Binary Search be used on an unsorted array?

No, Binary Search requires the array to be sorted in either ascending or descending order.

How do I handle edge cases in the Binary Search problem?

Edge cases include situations where the target is not found. In such cases, ensure to return -1 after exhausting the search space.

What are some variants of the Binary Search problem?

Variants include searching in a descending sorted array, finding the first occurrence of a target in a duplicate array, or searching for the closest value to the target.

How does GhostInterview help with Binary Search problems?

GhostInterview provides structured hints, solution explanations, and potential pitfalls, ensuring you're well-prepared for solving Binary Search in interviews.

terminal

Solution

Solution 1: Binary Search

We define the left boundary $l=0$ and the right boundary $r=n-1$ for binary search.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l < r:
            mid = (l + r) >> 1
            if nums[mid] >= target:
                r = mid
            else:
                l = mid + 1
        return l if nums[l] == target else -1

Continue Practicing

#710 random pick with blacklist #713 subarray product less than k #718 maximum length of repeated subarray