Binary Search
The key idea
Because
nums is sorted, one comparison against the middle element tells you which half can possibly contain target. Discard the other half and repeat, halving the search space each step — that is what gives O(log n).Problem
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.
The values in nums are distinct, so target can match at most one index.
Constraints
1 <= nums.length <= 10^4-10^4 < nums[i], target < 10^4- All the integers in
numsare unique. numsis sorted in ascending order.
Examples
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Complexity
Time: O(log n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Binary Search problems
- Capacity To Ship Packages Within D DaysMEDIUM
- Find First and Last Position of Element in Sorted ArrayMEDIUM
- Find in Mountain ArrayHARD
- Find K Closest ElementsMEDIUM
- Find Minimum in Rotated Sorted ArrayMEDIUM
- Find Peak ElementMEDIUM
- First Bad VersionEASY
- Guess Number Higher or LowerEASY
- Koko Eating BananasMEDIUM
- Lowest Common Ancestor of a Binary Search TreeMEDIUM
- Median of Two Sorted ArraysHARD
- Search a 2D MatrixMEDIUM