Skip to main content
Talentd

Binary Search - Solution & Explanation

EasyArrayBinary Search18 min readAsked at: Amazon, Microsoft, Meta +8
Practice this problem

Problem Statement

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

 

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

 

Constraints:

  • 1 <= nums.length <= 104
  • -104 < nums[i], target < 104
  • All the integers in nums are unique.
  • nums is sorted in ascending order.

Approach Overview

Problem Overview: Given a sorted integer array nums and a target, return the index of the target if it exists. If the value is not present, return -1. The key constraint is that the array is already sorted, which allows you to use binary search instead of scanning every element.

Approach 1: Linear Scan (Brute Force) (Time: O(n), Space: O(1))

The most direct approach is to iterate through the array from left to right and compare every element with target. The moment you find a match, return its index. If the loop finishes without finding the value, return -1. This works for any array, sorted or not, but it ignores the sorted property entirely. Each lookup may require scanning the entire array, so the time complexity grows linearly with n.

Approach 2: Iterative Binary Search (Time: O(log n), Space: O(1))

Binary search cuts the search space in half on every step. Start with two pointers: left = 0 and right = n - 1. Compute the middle index using mid = left + (right - left) / 2 to avoid overflow. If nums[mid] == target, return mid. If the middle value is smaller than the target, discard the left half by setting left = mid + 1. Otherwise discard the right half with right = mid - 1. Continue until the pointers cross. Because the search space halves each iteration, the time complexity is O(log n) and the algorithm uses O(1) extra space.

This iterative form is the most common implementation in production code. It avoids recursion overhead and keeps memory usage constant. Many interviewers prefer this version because it shows clear pointer control and correct boundary handling.

Approach 3: Recursive Binary Search (Time: O(log n), Space: O(log n))

The same halving logic can be expressed recursively. Define a function that takes left and right boundaries. Compute mid, compare with the target, and recursively search either the left or right half. The recursion stops when left > right. Each recursive call reduces the problem size by half, so the time complexity remains O(log n). However, recursion adds call stack overhead, giving it O(log n) auxiliary space.

This version is easier to reason about conceptually because the code mirrors the divide-and-conquer idea directly. It is also a good demonstration of recursion, though most engineers switch to the iterative version in performance-sensitive code.

Recommended for interviews: Iterative binary search is the expected solution. It demonstrates that you recognize the sorted array property and can reduce the search space efficiently to O(log n). Mentioning the linear scan shows baseline understanding, but implementing binary search correctly—especially pointer updates and midpoint calculation—demonstrates real algorithmic skill.

Approach 1: Iterative Binary Search

The iterative binary search approach involves using a loop to divide the array into halves repeatedly until the target is found or the search range is empty. This approach utilizes two pointers, 'low' and 'high', that represent the current search bounds.

This C code implements an iterative binary search. It uses a loop to adjust the low and high pointers based on comparisons, eventually finding the target or concluding it is not present.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log n), as we divide the search space in half each time.
Space Complexity: O(1), only a constant amount of space is used.

Try this approach in the editor →

Approach 2: Recursive Binary Search

The recursive binary search involves calling a function that repeatedly calls itself with updated bounds until the target is found or the bounds overlap. This approach provides a cleaner implementation at the cost of additional space used by the call stack.

This C solution uses recursion to split the problem into smaller subproblems, updating 'low' and 'high' in each recursive call.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log n)
Space Complexity: O(log n) due to the stack space used by recursion.

Try this approach in the editor →

Approach 3: Binary Search

We define the left boundary l=0 and the right boundary r=n-1 for binary search.

In each iteration, we calculate the middle position mid=(l+r)/2, then compare the size of nums[mid] and target.

  • If nums[mid] geq target, it means target is in the left half, so we move the right boundary r to mid;
  • Otherwise, it means target is in the right half, so we move the left boundary l to mid+1.

The loop ends when l<r, at this point nums[l] is the target value we are looking for. If nums[l]=target, return l; otherwise, return -1.

The time complexity is O(log n), where n is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Binary Search

Time Complexity: O(log n), as we divide the search space in half each time.
Space Complexity: O(1), only a constant amount of space is used.

Recursive Binary Search

Time Complexity: O(log n)
Space Complexity: O(log n) due to the stack space used by recursion.

Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Linear ScanO(n)O(1)When the array is unsorted or simplicity matters more than performance
Iterative Binary SearchO(log n)O(1)Best choice for sorted arrays and interview solutions
Recursive Binary SearchO(log n)O(log n)When demonstrating divide-and-conquer or recursion patterns

Video Solution

Binary Search - Leetcode 704 - Python • NeetCode • 267,520 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Binary Search easy or hard?
Binary search is classified as an easy problem on most coding platforms, but many candidates make mistakes with boundary updates or midpoint calculation. The concept is simple—halve the search space—but implementing it correctly and avoiding off-by-one errors requires practice.
Binary Search Python/Java solution
In Python or Java, implement binary search using two pointers and a loop. Compute the midpoint, compare with the target, and shrink the search range accordingly. Both languages achieve O(log n) time and O(1) space with the iterative implementation.
How to solve Binary Search in O(log n)?
Use the sorted property of the array. Maintain two pointers, left and right, compute the midpoint, and compare nums[mid] with the target. If the target is larger, move the left pointer to mid + 1; otherwise move the right pointer to mid - 1. Repeating this halving process reduces the search space exponentially, resulting in O(log n) time.
What is the best approach for Binary Search?
Iterative binary search is the best approach for this problem. It repeatedly halves the search range using two pointers and a midpoint check, achieving O(log n) time complexity with O(1) space. The iterative version avoids recursion overhead and is the most commonly expected implementation in interviews.
Is Binary Search asked at Google/Amazon/Meta?
Binary search is a fundamental algorithm frequently used in interviews at companies like Google, Amazon, and Meta. It often appears directly or as part of variations such as searching in rotated arrays, finding boundaries, or determining insertion positions in sorted data.
What data structure is used in Binary Search?
Binary search operates on a sorted array or any random-access structure that allows constant-time index lookup. Arrays are the most common structure because they support direct indexing, which is required to quickly access the midpoint during each step.
What is the time complexity of Binary Search?
Binary search runs in O(log n) time because the search space is cut in half after each comparison. For an array of size n, the algorithm performs at most log2(n) iterations. Space complexity is O(1) for the iterative version and O(log n) for the recursive version due to the call stack.

Ready to solve this problem?

Practice Binary Search with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Count of Positive Integer and Negative Integer

Next

Search in a Sorted Array of Unknown Size