Binary Search
- mosesg1123
- Apr 22
- 2 min read
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!
Comments