How do you solve Binary Search?

Initialize two pointers, left and right, at the start and end of the array. While left target, move right to mid - 1. Otherwise, move left to mid + 1. If the loop ends without finding target, return -1.

What pattern does Binary Search use?

The Pattern: Modified Binary Search The Heuristic: Binary Search exploits the sorted order by comparing the target to the middle element and discarding half the search space each iteration, ensuring O(log n) time complexity.

Binary Search - LeetCode Solution & Explanation

Q: What is the time complexity of Binary Search?

O(log n). Each iteration halves the search space by adjusting left or right pointers, leading to logarithmic time relative to the input size.

Problem

Given a sorted array of integers nums and an integer target, return the index of target if it exists in nums; otherwise, return -1.

1 ≤ nums.length ≤ 10⁴
−10⁴ ≤ nums[i], target ≤ 10⁴
nums is sorted in ascending order
All elements in nums are unique

Example

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

Output: 4

A brute-force linear scan would check each element until it finds 9 at index 4. This approach is O(n) and inefficient for large arrays. The optimal strategy uses binary search to repeatedly halve the search space, achieving O(log n) time. Starting with left=0 and right=5, the algorithm calculates mid=2 (value 3). Since 3 < 9, it moves left to mid+1=3. Now left=3, right=5, mid=4 (value 9). The target is found at index 4, and the algorithm returns immediately.

Approach

Straightforward Solution

A linear scan checks each element sequentially, resulting in O(n) time complexity, which is inefficient for large inputs.

Core Observation

In a sorted array, the relative order of elements allows us to discard half the search space at each step by comparing the target with the middle element.

Path to Optimal

The key recognition signals are 'sorted array' and 'find target index'. These indicate binary search because the sorted order enables halving the search space by comparing the target to the middle element. This reduces the search from O(n) to O(log n).

Optimal Approach

Initialize two pointers, left and right, at the start and end of the array. While left <= right, compute mid. If nums[mid] equals target, return mid. If nums[mid] > target, move right to mid - 1. Otherwise, move left to mid + 1. If the loop ends without finding target, return -1.

Time

O(log n)

Each iteration halves the search space by adjusting left or right pointers, leading to logarithmic time relative to the input size.

Space

O(1)

The algorithm uses a fixed number of variables for pointers and indices, requiring constant auxiliary space.

Solution

1class Solution:
  def search(self, nums: list[int], target: int) -> int:
      left, right = 0, len(nums) - 1
4
      while left <= right:
          mid = (left + right) // 2
          
          if nums[mid] > target:
              right = mid - 1
          elif nums[mid] < target:
              left = mid + 1
          else:
              return mid
      
      return -1

1class Solution {
  public int search(int[] nums, int target) {
      int left = 0;
      int right = nums.length - 1;
5
      while (left <= right) {
          int mid = left + (right - left) / 2;
8
          if (nums[mid] > target) {
              right = mid - 1;
          } else if (nums[mid] < target) {
              left = mid + 1;
          } else {
              return mid;
          }
      }
17
      return -1;
  }
20}

Step-by-Step Solution

1

Initialize Search Boundaries to Cover Entire Array

3	`left, right = 0, len(nums) - 1`

Objective

To set the initial search range covering the entire array.

Key Insight

Starting with left at 0 and right at the last index ensures the entire array is considered. This sets the stage for the binary search to progressively narrow down the search space.

Interview Quick-Check

Core Logic

left and right pointers define the current search boundaries, which shrink as the algorithm progresses.

State & Boundaries

left starts at 0 and right at len(nums) - 1 to cover the full array.

2

Iteratively Narrow Search Space by Comparing Midpoint to Target

5while left <= right:
  mid = (left + right) // 2
  if nums[mid] > target:
      right = mid - 1
  elif nums[mid] < target:
      left = mid + 1

Objective

To repeatedly halve the search space by comparing the middle element to the target and adjusting pointers accordingly.

Key Insight

Calculating mid as the average of left and right divides the current search range. Comparing nums[mid] to target determines which half can be discarded. This process continues until the target is found or the search space is empty.

Interview Quick-Check

Core Logic

At each iteration, the algorithm compares nums[mid] to target and moves either left or right pointer to discard half the search space.

State & Boundaries

The loop continues while left <= right, ensuring all possible indices are checked.

Common Pitfalls & Bugs

Using left < right instead of left <= right can miss the case where left == right, potentially skipping the last element.

3

Return Index Immediately Upon Finding Target

12else:
13    return mid

Objective

To terminate the search and return the index as soon as the target is found.

Key Insight

Once nums[mid] equals target, the search is complete. Returning immediately avoids unnecessary further iterations and guarantees the correct index is returned.

Interview Quick-Check

Core Logic

Returning mid immediately upon match ensures the algorithm stops at the first occurrence of the target.

4

Return -1 When Target Is Not Found After Exhausting Search Space

15	`return -1`

Objective

To indicate the target does not exist in the array by returning -1 after the search space is fully explored.

Key Insight

If the loop terminates without finding the target, it means the target is not present. Returning -1 signals this absence clearly and unambiguously.

Interview Quick-Check

Core Logic

Returning -1 after the loop confirms the target is not in the array.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 12 Critical

else:

Check if the middle element equals the target.

Finding nums[mid] == target means the search is successful and the index mid is the correct answer to return.

Line 8 Critical

if nums[mid] > target:

Check if the middle element is greater than the target.

If nums[mid] > target, the target must lie to the left of mid, so the right pointer is moved to mid - 1 to discard the right half.

Line 10 Critical

elif nums[mid] < target:

Check if the middle element is less than the target.

If nums[mid] < target, the target must lie to the right of mid, so the left pointer is moved to mid + 1 to discard the left half.

Line 13 Critical

return mid

Return the index of the found target.

Returning mid immediately terminates the search and provides the exact position of the target in the array.

Line 5 Core

while left <= right:

Start a loop that continues while the search space is valid.

The condition left <= right ensures that the search space includes all possible indices, including when left equals right, preventing missing the last candidate.

Line 6 Core

mid = (left + right) // 2

Calculate the middle index of the current search range.

Computing mid as the integer division of (left + right) splits the search space into two halves, enabling binary search's divide-and-conquer approach.

Line 9 Core

right = mid - 1

Update right pointer to narrow the search to the left half.

Moving right to mid - 1 discards the current mid and all elements to its right, focusing the search on the left subarray where the target may exist.

Line 11 Core

left = mid + 1

Update left pointer to narrow the search to the right half.

Moving left to mid + 1 discards the current mid and all elements to its left, focusing the search on the right subarray where the target may exist.

Line 3 Core

left, right = 0, len(nums) - 1

Initialize left and right pointers to cover the entire array.

Setting left to 0 and right to len(nums) - 1 defines the initial search boundaries, ensuring the entire array is considered for the target.

Line 15 Core

return -1

Return -1 if the target is not found after the loop ends.

Returning -1 signals that the target does not exist in the array, as the search space has been exhausted without a match.

Test Your Understanding

Why does binary search update the pointers based on comparisons with the middle element rather than scanning sequentially?

Because the array is sorted, comparing the target with the middle element allows discarding half the search space where the target cannot exist, drastically reducing the number of comparisons needed.

Don't just read it. Drill it.

Reconstruct Binary Search from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Binary Search drill

or drill a free problem

1	`class Solution:`
2	`def search(self, nums: list[int], target: int) -> int:`
3	`left, right = 0, len(nums) - 1`
4
5	`while left <= right:`
6	`mid = (left + right) // 2`
7
8	`if nums[mid] > target:`
9	`right = mid - 1`
10	`elif nums[mid] < target:`
11	`left = mid + 1`
12	`else:`
13	`return mid`
14
15	`return -1`

1	`class Solution {`
2	`public int search(int[] nums, int target) {`
3	`int left = 0;`
4	`int right = nums.length - 1;`
5
6	`while (left <= right) {`
7	`int mid = left + (right - left) / 2;`
8
9	`if (nums[mid] > target) {`
10	`right = mid - 1;`
11	`} else if (nums[mid] < target) {`
12	`left = mid + 1;`
13	`} else {`
14	`return mid;`
15	`}`
16	`}`
17
18	`return -1;`
19	`}`
20	`}`

5	`while left <= right:`
6	`mid = (left + right) // 2`
8	`if nums[mid] > target:`
9	`right = mid - 1`
10	`elif nums[mid] < target:`
11	`left = mid + 1`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Search Boundaries to Cover Entire Array

Iteratively Narrow Search Space by Comparing Midpoint to Target

Return Index Immediately Upon Finding Target

Return -1 When Target Is Not Found After Exhausting Search Space

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.