mafeshsho8lmafeshsho8l
Get Started
All coding questions

Binary Search

easy
NeetCode 150binary-searcharrays

Problem

Given a list of integers sorted ascending and a target, return the index of the target if present, otherwise negative one. The search must run in logarithmic time.

Examples

Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
The target sits at index four.
Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1
Two is absent.

Constraints

  • • 1 <= nums.length <= 10^4
  • • Array is sorted ascending with unique values
Hints(tap to reveal)
  • 1. Halve the search range each step.
  • 2. Be careful computing the midpoint to avoid overflow.
Optimal approach(spoiler)
  1. Keep a low and high boundary over the array.
  2. Inspect the middle element each iteration.
  3. Narrow to the left or right half based on the comparison.
  4. Stop when the boundaries cross or the target is found.
  5. O(log n) time, O(1) space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor