Binary Search

Asked byAmazonAppleGoogleMicrosoftBloombergAdobe

Problem

Given a sorted array of unique integers and a target, return the index of the target if it exists, or -1 otherwise, in O(log n) time.

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

Constraints

1 <= nums.length <= 10^4
nums is sorted in ascending order with unique values.

Try it now — no sign-up needed. Write your solution in Python or JavaScript, run it against test cases, and submit for a verdict, right in your browser.

Open the editor →

How to approach it: the Binary Search pattern

Repeatedly halve the search space by comparing the middle element to a target, turning an O(n) scan into O(log n). It works on more than sorted arrays — any "answer space" that's monotonic (true…true…false…false) can be binary searched.

Look for this pattern when

The input is sorted, or partially sorted (like a rotated sorted array).
You're minimizing or maximizing a value where "is X feasible?" is easy to check and feasibility is monotonic.

Read the full Binary Search guide →

Video walkthroughs

Original problem on LeetCode ↗