How do you solve Binary Search on LeetCode?

Binary Search (LeetCode #704) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(log n) time complexity and O(1) space complexity. Key insight: Binary search is efficient for sorted arrays.

What is the brute force solution for Binary Search?

The brute force approach for Binary Search is Brute Force, with O(n) time complexity and O(1) space complexity. The brute force approach involves checking each element in the array one by one until we find the target. This is straightforward but inefficient for large arrays. The optimal Optimal Solution approach improves this to O(log n).

What algorithm or data structure is used to solve Binary Search?

Binary Search uses the following concepts: Array, Binary Search. The recommended patterns to study are: Binary Search, Divide and Conquer.

What are the interview tips for Binary Search?

Explain your thought process clearly. Mention edge cases, such as when the target is not present. Practice writing both brute force and optimal solutions.

What are common mistakes when solving Binary Search?

Not checking the middle element correctly. Forgetting to update left or right pointers properly.

#704

Binary Search

Easy

ArrayBinary SearchBinary SearchDivide and Conquer

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n)	O(log n)
Space	O(1)	O(1)

💡

Intuition

Time O(log n)Space O(1)

The optimal solution uses binary search, which efficiently narrows down the search space by repeatedly dividing the array in half. This is much faster than checking each element one by one.

⚙️

Algorithm

6 steps

1Step 1: Initialize two pointers, left at 0 and right at the last index of the array.
2Step 2: While left is less than or equal to right, calculate the middle index.
3Step 3: If the middle element equals the target, return the middle index.
4Step 4: If the middle element is less than the target, move the left pointer to mid + 1.
5Step 5: If the middle element is greater than the target, move the right pointer to mid - 1.
6Step 6: If the target is not found, return -1.

solution.py11 lines

1def search(nums, target):
2    left, right = 0, len(nums) - 1
3    while left <= right:
4        mid = left + (right - left) // 2
5        if nums[mid] == target:
6            return mid
7        elif nums[mid] < target:
8            left = mid + 1
9        else:
10            right = mid - 1
11    return -1

ℹ

Complexity note: This complexity is achieved because each step reduces the search space by half, leading to logarithmic time complexity.

1Binary search is efficient for sorted arrays.
2Understanding how to adjust pointers is crucial for binary search.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.