How to Solve: Binary Search (Basic, First and Last Occurrence) – Complete Guide for FAANG Interviews

How to Solve: Binary Search (Basic, First and Last Occurrence) – Complete Guide for FAANG Interviews

? Introduction

"Binary search isn’t just about finding a number—it’s the fastest way to prove you can write clean, efficient code under pressure. FAANG interviewers use it to test your ability to handle edge cases, optimize brute-force solutions, and think in logarithmic time. Master this, and you’ll solve 1 in 4 medium/hard problems in under 30 minutes."

? WHAT YOU NEED TO KNOW FIRST

Before diving into binary search, ensure you understand: 1. Sorted Arrays – Binary search only works on sorted data (or data that can be partitioned in a sorted way). 2. Time Complexity – O(log n) vs. O(n) and why it matters in interviews. 3. Loop Invariants – How to maintain correctness in while loops (e.g., left <= right vs. left < right).

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Run this every time you see a binary search problem:

1. Confirm the input is sorted (or can be partitioned sorted).

2. If not, ask: "Can I sort it first?" (If yes, sort and proceed. If no, binary search is likely not the answer.)

3. Define left and right pointers.

4. left = 0, right = len(nums) - 1 (for full array search).

5. For subarrays, adjust left and right accordingly.

6. Choose the loop condition:

7. while left <= right: Use when you need to check mid against target (e.g., basic search).

8. while left < right: Use when you’re narrowing the search space (e.g., first/last occurrence).

9. Calculate mid safely to avoid overflow.

10. mid = left + (right - left) // 2 (never left + right // 2).

11. Decide how to move left and right:

12. If nums[mid] < target → left = mid + 1 (search right half).
13. If nums[mid] > target → right = mid - 1 (search left half).

14. If nums[mid] == target → depends on the problem (e.g., return mid, or search left/right for first/last occurrence).

15. Handle edge cases:

16. Empty array → return -1 or None.
17. Single-element array → check if it matches the target.

18. All elements equal → ensure the loop terminates.

19. Test with small examples:

20. [1,3,5], target = 3 → should return 1.
21. [1,1,1], target = 1 → should return 0 (first occurrence) or 2 (last occurrence).

? WORKED EXAMPLES

Example 1 – Basic Binary Search

Problem: Given a sorted array nums and a target target, return the index of target if it exists, else -1.

Framework Application: 1. Input is sorted → proceed. 2. left = 0, right = len(nums) - 1. 3. Loop condition: while left <= right. 4. mid = left + (right - left) // 2. 5. If nums[mid] == target → return mid.
- If nums[mid] < target → left = mid + 1.
- If nums[mid] > target → right = mid - 1. 6. If loop ends → return -1.

Code (Python):

def search(nums, target):

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

    while left <= right:

        mid = left + (right - left) // 2

        if nums[mid] == target:

            return mid

        elif nums[mid] < target:

            left = mid + 1

        else:

            right = mid - 1

    return -1

Time Complexity: O(log n) Space Complexity: O(1)

Why this works: - The loop halves the search space each iteration, ensuring logarithmic time. - The left <= right condition ensures we check every possible element.

Example 2 – First Occurrence (Medium)

Problem: Given a sorted array nums with duplicates, return the first occurrence of target. If not found, return -1.

Framework Application: 1. Input is sorted → proceed. 2. left = 0, right = len(nums) - 1. 3. Loop condition: while left <= right. 4. mid = left + (right - left) // 2. 5. If nums[mid] == target → record mid and search left for earlier occurrences (right = mid - 1).
- If nums[mid] < target → left = mid + 1.
- If nums[mid] > target → right = mid - 1. 6. Return the recorded index (or -1 if not found).

Code (Python):

def first_occurrence(nums, target):

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

    result = -1

    while left <= right:

        mid = left + (right - left) // 2

        if nums[mid] == target:

            result = mid

            right = mid - 1  # Search left for earlier occurrence

        elif nums[mid] < target:

            left = mid + 1

        else:

            right = mid - 1

    return result

Time Complexity: O(log n) Space Complexity: O(1)

Why this works: - When we find target, we don’t return immediately—we keep searching left to find the first occurrence. - The result variable tracks the earliest valid index.

Example 3 – Last Occurrence (Hard/Follow-up)

Problem: Given a sorted array nums with duplicates, return the last occurrence of target. If not found, return -1.

Framework Application: 1. Input is sorted → proceed. 2. left = 0, right = len(nums) - 1. 3. Loop condition: while left <= right. 4. mid = left + (right - left) // 2. 5. If nums[mid] == target → record mid and search right for later occurrences (left = mid + 1).
- If nums[mid] < target → left = mid + 1.
- If nums[mid] > target → right = mid - 1. 6. Return the recorded index (or -1 if not found).

Code (Python):

def last_occurrence(nums, target):

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

    result = -1

    while left <= right:

        mid = left + (right - left) // 2

        if nums[mid] == target:

            result = mid

            left = mid + 1  # Search right for later occurrence

        elif nums[mid] < target:

            left = mid + 1

        else:

            right = mid - 1

    return result

Time Complexity: O(log n) Space Complexity: O(1)

Why this works: - Similar to first occurrence, but we search right after finding target to find the last occurrence. - The result variable tracks the latest valid index.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. Binary search is all about halving the search space in logarithmic time. Here’s your 30-second checklist:

1. Confirm the input is sorted—if not, binary search won’t work.
2. Set left and right—start with 0 and len(nums) - 1.
3. Choose your loop condition—left <= right for basic search, left < right for narrowing.
4. Calculate mid safely—left + (right - left) // 2 to avoid overflow.
5. Move pointers correctly—if nums[mid] < target, search right; if nums[mid] > target, search left.
6. For first/last occurrence, don’t return early—keep searching left or right.
7. Test edge cases—empty array, single element, all duplicates.

Now go crush that interview. You’ve got this!

? Final Notes

• Practice on LeetCode: Solve 704. Binary Search, 34. Find First and Last Position of Element in Sorted Array, and 33. Search in Rotated Sorted Array.
• Whiteboard first: Always sketch the array and pointers before coding.
• Time yourself: Aim for under 15 minutes per problem in mock interviews.

Good luck! ?