704. Binary Search — LeetCode(Python)
I got you!
Given an array of integers
nums which is sorted in ascending order, and an integer
target, write a function to search
target exists, then return its index. Otherwise, return
You must write an algorithm with
O(log n) runtime complexity.
Input: nums = [-1,0,3,5,9,12], target = 9
Explanation: 9 exists in nums and its index is 4
Input: nums = [-1,0,3,5,9,12], target = 2
Explanation: 2 does not exist in nums so return -1
1 <= nums.length <= 104
-104 < nums[i], target < 104
- All the integers in
numsis sorted in ascending order.
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
elif nums[mid] < target:
l = mid + 1
r = mid - 1
The algorithm is pretty standard. We create two pointers on left and right ends of our array nums.
Then we calculate our array’s mid element.
If this index contains the target value, we return this index.
Since, we know that the array is sorted, we check if the target value is greater than the element we’re at. If yes, we check only the right subarray, which has larger values than nums[mid]. We accomplish this by shifting our left pointer to the index after mid.
And if the target value is less than our current element, we only check the left subarray, which has smaller values than nums[mid]. We accomplish this by shifting our right pointer to the index before mid.
If we don’t come across the target value in the array, we return -1.
Time and Space Complexity:
We are dividing the array into equal halves on every iteration, until only a single number is left in the array, after which our termination l ≤ r becomes False.
And, we know, the number of times we can divide a number by two to reach one, is log2(n). [2 is the base]
We also note that we require a constant amount of extra space for our algorithm.
Thus, if n is the length of the array nums,
Time Complexity: O(log(n))
Space Complexity: O(1)