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 — Modified Binary Search

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

Preview

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…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Initialize two pointers, left and right, at the start and end of the array. While left <= right, compute mid…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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

Python

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

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

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

3

Return Index Immediately Upon Finding Target

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

4

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

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

3 more steps with full analysis available on Pro.

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.

Full line-by-line criticality + rationale for all 10 lines available on Pro.

Test Your Understanding

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

See the answer with Pro.

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`