Binary Search

Binary Search is a cornerstone algorithm that shows up in everything from database lookups to system libraries. It’s a perfect warm‑up for interviews because it tests your ability to leverage sorted data for logarithmic‑time performance and handle edge cases precisely.

Problem Statement

Given a sorted array of integers nums and an integer target, return the index of target if it exists in the array. If it does not exist, return -1. The solution must run in O(log n) time.

1. Clarify Requirements Before Jumping Into Code

Let me make sure I have all the details straight:

• Array is sorted in ascending order

• No duplicates? Even if duplicates exist, returning any matching index is fine

• Must be O(log n) time

• Return -1 if target not found

• Array length can be zero

That covers it.

2. Identify the Category of the Question

Sorted array + O(log n) requirement = classic binary search. This problem falls under divide‑and‑conquer search patterns.

3. Consider a Brute‑Force Approach to Understand the Problem

Brute force would be a linear scan:

for i from 0 to length(nums)-1:
    if nums[i] == target:
        return i
return -1

Time complexity O(n), space O(1). It works but fails the O(log n) requirement.

4. Brainstorm More Solutions

Options include:

• Binary Search (Iterative): Maintain left/right pointers, compare mid, adjust boundaries.

• Binary Search (Recursive): Similar logic via recursion.

No hash maps, no two‑pointers—this is pure binary search.

5. Discuss Trade‑Offs Between Your Solutions

Approach	Time	Space	Pros	Cons
Linear Scan	O(n)	O(1)	Simple	Too slow for large n
Iterative Binary	O(log n)	O(1)	Fast, no recursion overhead	Slightly more logic
Recursive Binary	O(log n)	O(log n)	Clear recursion structure	Uses call stack space

Iterative binary search is best: meets time, space, and simplicity goals.

6. Write Pseudocode to Structure Your Thoughts

function binarySearch(nums, target):
    left = 0
    right = length(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        else if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

7. Consider Edge Cases

• Empty array → return -1

• Single‑element array matching target → return 0

• Single‑element array not matching → return -1

• Target less than all elements → return -1

• Target greater than all elements → return -1

• Duplicates in array → returns any matching index

8. Write Full Code Syntax

def binary_search(nums, target):
    left, right = 0, len(nums) - 1

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

    return -1

9. Test Your Code

assert binary_search([], 5) == -1
assert binary_search([1], 1) == 0
assert binary_search([1], 2) == -1
assert binary_search([1, 3, 5, 7], 5) == 2
assert binary_search([1, 3, 5, 7], 2) == -1
assert binary_search([2, 4, 6, 8, 10], 10) == 4
assert binary_search([2, 4, 6, 8, 10], 1) == -1

print("All tests passed!")

10. Key Lessons to Remember for Future Questions

• Recognize sorted + O(log n) → binary search instantly.

• Pay careful attention to loop conditions (left <= right) to avoid infinite loops.

• Iterative approach avoids stack overhead of recursion in tight loops.

Good Luck and Happy Coding!