#704 Binary Search
You have an array of integers sorted in ascending order, with no duplicates,
and a value target. Return the index where target sits in the array, or
-1 if it isn't there. Your algorithm must run in O(log n). A linear
scan doesn't count.
Examples
Input
nums = [-1, 0, 3, 5, 9, 12], target = 9Output
4nums[4] = 9.
Input
nums = [-1, 0, 3, 5, 9, 12], target = 2Output
-12 would belong between 0 and 3, but it isn't present, return -1.
Constraints
1 ≤ nums.length ≤ 10⁴-10⁴ < nums[i], target < 10⁴nums is sorted ascending with all values distinct
The explainer is the good part.
Sign in for the full intuition build-up, every approach from naive to optimal with complexity analysis, progressive hints, and commented solutions in Python, JavaScript, and Java. All free.
Want a taste first? Try a free sample: Two Sum or Valid Parentheses.