DSA-VerseLearn by watching code run
DashboardData StructuresAlgorithmsVisualizerCORECoding PlaygroundInterview QuestionsComplexity AnalyzerLearning NotesBookmarksLearning ProgressSettings
All interview questions

Interview preparation

Binary Search

EasyArraysSorting and Searching
GoogleMicrosoftAdobe Community-reported practice tags — not verified company questions.

1Problem statement

Given a sorted (ascending) array of distinct integers nums and a target, return the index of target, or −1 if it is not present. Your algorithm must run in O(log n) time.

2Examples

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1

3Constraints

  • 1 ≤ nums.length ≤ 10⁴
  • All values are unique and sorted ascending.

4Approaches

Approach 1

Brute Force

Linear scan comparing each element with target.

Time O(n)Space O(1)

Approach 2

Better: Recursive binary search

Recurse into the half that can contain the target.

Time O(log n)Space O(log n)

Approach 3

Optimal: Iterative binary search

Maintain [low, high]; compare with mid and discard half of the range each iteration.

Time O(log n)Space O(1)

5Code (optimal approach)

Complete programs that print the example outputs — verified in JavaScript, Python, Java and Go.

function search(nums, target) {
  let low = 0;
  let high = nums.length - 1;
  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

console.log(search([-1, 0, 3, 5, 9, 12], 9));
console.log(search([-1, 0, 3, 5, 9, 12], 2));

6Complexity

Time

O(log n)

Space

O(1)

7Visual walkthrough

Step through this exact algorithm:

Binary Searchinteractive Open full visualizer
2
5
8
12
16
23
38
56
72
91
0
1
2
3
4
5
6
7
8
9
ComparingSwapping / movingCurrentSorted / finalFound / placed

Searches a sorted array by repeatedly comparing the target with the middle element and discarding the half that cannot contain it.

1 / 17

8Related questions

Two Sum

On this page

  1. 01Problem statement
  2. 02Examples
  3. 03Constraints
  4. 04Approaches
  5. 05Code (4 languages)
  6. 06Complexity
  7. 07Visual walkthrough
  8. 08Related questions