Binary Search Questions at American Express: What to Expect

Binary Search is a core algorithmic technique that American Express assesses in their technical interviews. With 2 out of 24 questions typically focused on this pattern, it’s a significant component of their coding screen. Mastery here demonstrates efficient problem-solving with sorted data—a skill directly applicable to financial data processing, transaction analysis, and optimizing large-scale systems where performance is critical.

What to Expect — Types of Problems

American Express typically presents Binary Search in two forms. First, classic array-based searches where you locate a target in a sorted list or a rotated sorted array. Second, applied problems on answer spaces, where you search for an optimal value (like a minimum time, maximum capacity, or a specific threshold) within a bounded range. These often involve checking a feasibility condition at each step. Expect constraints that require O(log n) time, ruling out linear scans. Problems may be disguised; recognizing the sorted property or monotonic condition is key.

How to Prepare — Study Tips with One Code Example

Focus on the pattern, not memorization. Internalize the loop invariants and termination conditions to avoid off-by-one errors. Practice writing iterative Binary Search flawlessly, then adapt it for rotated arrays or predicate-based searches. Always clarify input characteristics (sorted? duplicates?) and edge cases (empty array, single element, target absent).

A key pattern is searching in a rotated sorted array, where the array is sorted but rotated at an unknown pivot. The approach compares the mid-element with the boundaries to determine which side is sorted, then narrows the search.

def search_rotated(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        # Left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

Recommended Practice Order

Start with the classic Binary Search on a sorted array to build muscle memory. Then move to variants: finding first/last occurrence, search in a rotated array, and finding minimum in rotated array. Progress to answer space problems like capacity planning or splitting arrays, where you implement a feasibility check. Finally, tackle 2D matrix searches (rows and columns sorted). Time yourself to simulate interview pressure.

Practice Binary Search at American Express