Loading…
Binary Search is a easy coding interview question covering binary search, arrays — the kind asked at FAANG (Facebook/Meta, Apple, Amazon, Netflix, Google) and AI-first companies like Anthropic, OpenAI, and Nvidia.
Given an array of integers `nums` sorted in ascending order, and an integer `target`, write a function to search for `target`. Return its index if found, otherwise return -1.
You must write an algorithm with O(log n) runtime complexity.
Try it yourself first
In an interview you'd get about 15 minutes for a easy question. Sketch an approach before peeking — struggling is where the learning happens.
Stuck? Reveal them one at a time — each hint gives away a little more.
Ready to compare notes? The full solution, visualization, and complexity analysis are below.
Variables
| 1 | def binary_search(nums, target): |
| ▶ | left, right = 0, len(nums) - 1 |
| 3 | while left <= right: |
| 4 | mid = left + (right - left) // 2 |
| 5 | if nums[mid] == target: |
| 6 | return mid |
| 7 | elif nums[mid] < target: |
| 8 | left = mid + 1 |
| 9 | else: |
| 10 | right = mid - 1 |
| 11 | return -1 |
Initialize two pointers: left = 0 (start) and right = 5 (end). We search within this range.
Time
O(log n)
Space
O(1)
Scan the array from left to right
O(n) time, O(1) space
It works, and it throws away the single most useful thing the problem told you - that the input is sorted. On a million elements this is a million comparisons against binary search's twenty.
Recursive binary search
O(log n) time, O(log n) space
Same number of comparisons and often easier to read, but each level costs a stack frame, so the space is no longer constant. Reach for the iterative form when the interviewer asks for O(1) space - and expect them to ask.
Use two pointers (left=0, right=n-1). While left<=right: compute mid, compare nums[mid] to target. If equal return mid. If target > nums[mid], move left. Otherwise move right. Return -1 if not found.
A full interview loop is more than one round. These are the others, each with what is on the site for it.