easyBinary searchArrays
Search a Sorted Array
Find a target's index in a sorted array in logarithmic time, or return -1. Binary search is short to write and easy to get subtly wrong, which is why interviewers love it.
By Deepak KumarTests checked by DeepakJavaScript or Python
Given an array nums of distinct integers sorted in ascending order and an integer target, return the index of target, or -1 if it isn't in the array.
Your solution must run in O(log n) time.
Examples
Example 1
Input: nums = [-3, 0, 4, 9, 12], target = 9 Output: 3
Example 2
Input: nums = [-3, 0, 4, 9, 12], target = 5 Output: -1
Constraints
0 <= nums.length <= 10^5- All values are distinct and sorted ascending
Hints
Hint 1
Compare the target with the middle element. Which half can you throw away?
Hint 2
Keep a search range [lo, hi]. Stop when the range is empty; be careful to move lo and hi past mid so the loop always shrinks.
Solution
Show the solution (try it yourself first)
Approach: binary search
Because the array is sorted, comparing the target with the middle element tells you which half can't contain it. Keep a range [lo, hi] and halve it each step until you find the target or the range is empty. The bugs interviewers look for: using lo < hi instead of lo <= hi (missing a one-element range), setting lo = mid instead of mid + 1 (an infinite loop), and not handling an empty array.
def search_sorted(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1Complexity
Time O(log n): 100,000 items need at most 17 comparisons. Space O(1). In languages with fixed-size integers, lo + (hi - lo) / 2 avoids overflow when computing the middle.