Skip to main content

8. Binary Search

easyAsked at Redis

Implement classic binary search on a sorted array; Redis uses it to confirm log-time intuition before discussing skiplist random-level shortcuts.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a sorted (ascending) integer array nums and an integer target, return the index of target in nums, or -1 if it is not present. Must run in O(log n) time.

Constraints

  • 1 <= nums.length <= 10^4
  • All values unique
  • Array is sorted ascending

Examples

Example 1

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

Example 2

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

Approaches

1. Linear scan

Walk the array left to right.

Time
O(n)
Space
O(1)
for (let i = 0; i < nums.length; i++)
  if (nums[i] === target) return i;
return -1;

Tradeoff:

2. Iterative half-interval search

Maintain lo/hi pointers and halve the search window. Mirrors how Redis ZRANGEBYSCORE drives a skiplist by binary-stepping through level pointers.

Time
O(log n)
Space
O(1)
function search(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

Tradeoff:

Redis-specific tips

Redis interviewers want to hear how the skiplist achieves log-N range search with randomized level pointers — name-drop ZRANGEBYSCORE and the level-by-level descent.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Binary Search and other Redis interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →