Problems

Master the Binary Search pattern by applying it to these real-world interview challenges. For the standard implementations, refer to the Code Templates.

Easy Problems

1. Binary Search

Brief: Locate a target integer in a sorted array and return its index.
Why this pattern?: This is the textbook application of binary search—finding a value in a sorted array in
O(log N)
time.
Key Insight: Always use left + (right - left) / 2 to avoid integer overflow and ensure your left and right pointers correctly encapsulate the target if it exists.

  graph TD
    Start[Start] --> Loop{"left <= right?"}
    Loop -->|Yes| B[Calculate mid]
    B --> C{"nums[mid] == target?"}
    C -->|Yes| D[Return mid]
    C -->|No| E{"nums[mid] < target?"}
    E -->|Yes| F[left = mid + 1]
    E -->|No| G[right = mid - 1]
    F --> Loop
    G --> Loop
    Loop -->|No| End[Return -1]

JavaScript:

function search(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        let mid = left + Math.floor((right - left) / 2);
        if (nums[mid] === target) return mid;
        if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Python:

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

Java:

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

C++:

int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Go:

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

Ruby:

def search(nums, target)
  left, right = 0, nums.length - 1
  while left <= right
    mid = left + (right - left) / 2
    return mid if nums[mid] == target
    if nums[mid] < target
      left = mid + 1
    else
      right = mid - 1
    end
  end
  -1
end

2. Search Insert Position

Brief: Find the index of a target or the index where it should be inserted to maintain sorted order.
Why this pattern?: This evaluates your ability to find an insertion point (lower bound), a common variation of binary search.
Key Insight: Use while (left < right) and right = mid. In this variation, the loop terminates exactly at the index where the target is or should be.

  graph TD
    Start[Start] --> Loop{"left < right?"}
    Loop -->|Yes| B[Calculate mid]
    B --> C{"nums[mid] < target?"}
    C -->|Yes| D[left = mid + 1]
    C -->|No| E[right = mid]
    D --> Loop
    E --> Loop
    Loop -->|No| End[Return left]

JavaScript:

function searchInsert(nums, target) {
    let left = 0, right = nums.length;
    while (left < right) {
        let mid = left + Math.floor((right - left) / 2);
        if (nums[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
}

Python:

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

Java:

public int searchInsert(int[] nums, int target) {
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
}

C++:

int searchInsert(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
}

Go:

func searchInsert(nums []int, target int) int {
    left, right := 0, len(nums)
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

Ruby:

def search_insert(nums, target)
  left, right = 0, nums.length
  while left < right
    mid = left + (right - left) / 2
    if nums[mid] < target
      left = mid + 1
    else
      right = mid
    end
  end
  left
end

Medium Problems

3. First and Last Position of Element in Sorted Array

Brief: Find the starting and ending indices of a target in an array with duplicates.
Why this pattern?: Demonstrates search refinement. After finding the target, you keep searching in one direction to find the boundary.
Key Insight: Run the binary search twice. In the first run, when nums[mid] == target, move right = mid - 1 to keep looking left. In the second run, move left = mid + 1 to keep looking right.

  graph TD
    Start[Start Search] --> Found{"target found?"}
    Found -->|Yes| Record[Record index]
    Record --> First{"Searching First?"}
    First -->|Yes| MoveLeft[right = mid - 1]
    First -->|No| MoveRight[left = mid + 1]
    MoveLeft --> Start
    MoveRight --> Start
    Found -->|No| Done[End search]

JavaScript:

function searchRange(nums, target) {
    const findBound = (isFirst) => {
        let left = 0, right = nums.length - 1, result = -1;
        while (left <= right) {
            let mid = left + Math.floor((right - left) / 2);
            if (nums[mid] === target) {
                result = mid;
                if (isFirst) right = mid - 1;
                else left = mid + 1;
            } else if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return result;
    };
    return [findBound(true), findBound(false)];
}

Python:

def searchRange(nums: list[int], target: int) -> list[int]:
    def findBound(isFirst):
        left, right = 0, len(nums) - 1
        result = -1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                result = mid
                if isFirst: right = mid - 1
                else: left = mid + 1
            elif nums[mid] < target: left = mid + 1
            else: right = mid - 1
        return result
    return [findBound(True), findBound(False)]

Java:

public int[] searchRange(int[] nums, int target) {
    int first = findBound(nums, target, true);
    int last = findBound(nums, target, false);
    return new int[]{first, last};
}

private int findBound(int[] nums, int target, boolean isFirst) {
    int left = 0, right = nums.length - 1, result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            result = mid;
            if (isFirst) right = mid - 1;
            else left = mid + 1;
        } else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return result;
}

C++:

vector<int> searchRange(vector<int>& nums, int target) {
    return {findBound(nums, target, true), findBound(nums, target, false)};
}

int findBound(vector<int>& nums, int target, bool isFirst) {
    int left = 0, right = nums.size() - 1, result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            result = mid;
            if (isFirst) right = mid - 1;
            else left = mid + 1;
        } else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return result;
}

Go:

func searchRange(nums []int, target int) []int {
    return []int{findBound(nums, target, true), findBound(nums, target, false)}
}

func findBound(nums []int, target int, isFirst bool) int {
    left, right := 0, len(nums)-1
    result := -1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            result = mid
            if isFirst {
                right = mid-1
            } else {
                left = mid+1
            }
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return result
}

Ruby:

def search_range(nums, target)
  [find_bound(nums, target, true), find_bound(nums, target, false)]
end

def find_bound(nums, target, is_first)
  left, right = 0, nums.length - 1
  result = -1
  while left <= right
    mid = left + (right - left) / 2
    if nums[mid] == target
      result = mid
      is_first ? right = mid - 1 : left = mid + 1
    elsif nums[mid] < target
      left = mid + 1
    else
      right = mid - 1
    end
  end
  result
end

4. Search in Rotated Sorted Array

Brief: Search for a target in a sorted array that has been rotated at some unknown pivot.
Why this pattern?: This is a classic “Condition-based” binary search. You use the sorted property of half the array to decide your next step.
Key Insight: One half of the array (left to mid OR mid to right) must be sorted. If the sorted half contains the target, go there; otherwise, search the other half.

  graph TD
    Start[Calculate mid] --> Sorted{"Left Half Sorted?"}
    Sorted -->|Yes| RangeL{"target in Range?"}
    Sorted -->|No| RangeR{"target in Range?"}
    RangeL -->|Yes| D[right = mid - 1]
    RangeL -->|No| E[left = mid + 1]
    RangeR -->|Yes| G[left = mid + 1]
    RangeR -->|No| H[right = mid - 1]

JavaScript:

function search(nums, target) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        let mid = left + Math.floor((right - left) / 2);
        if (nums[mid] === target) return mid;
        if (nums[left] <= nums[mid]) { // Left half is sorted
            if (target >= nums[left] && target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        } else { // Right half is sorted
            if (target > nums[mid] && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}

Python:

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

Java:

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

C++:

int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        if (nums[left] <= nums[mid]) {
            if (target >= nums[left] && target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        } else {
            if (target > nums[mid] && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}

Go:

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        }
        if nums[left] <= nums[mid] {
            if target >= nums[left] && target < nums[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            if target > nums[mid] && target <= nums[right] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }
    return -1
}

Ruby:

def search(nums, target)
  left, right = 0, nums.length - 1
  while left <= right
    mid = left + (right - left) / 2
    return mid if nums[mid] == target
    if nums[left] <= nums[mid]
      if target >= nums[left] && target < nums[mid]
        right = mid - 1
      else
        left = mid + 1
      end
    else
      if target > nums[mid] && target <= nums[right]
        left = mid + 1
      else
        right = mid - 1
      end
    end
  end
  -1
end

Recommended Study Order

Binary Search: Understand the core iterative logic.
Search Insert Position: Learn how to handle “insertion points” and different boundary conditions.
First and Last Position: Master the technique of refining a search once a match is found.
Search in Rotated Sorted Array: Learn to identify and search partial order within nonlinear data.