Binary Search (LeetCode)
- 1 min read
- LC-Medium
- Binary-search
3 years ago
Both of the solutions below are the exact same, but just different ways to do it.
| Time | Space | Explanation |
|---|---|---|
O(n log n) | O(1) |
Solution 1
def search(self, nums: List[int], target: int) -> int:
start, end = 0, len(nums) - 1
while start <= end:
mid = (start + end) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
start = mid + 1
else:
end = mid - 1
return - 1
Solution 2
def search(self, nums: List[int], target: int) -> int:
start, end = 0, len(nums) - 1
while start < end:
mid = start + ((end - start + 1) // 2)
if target < nums[mid]:
end = mid - 1
else:
start = mid
return start if nums[start] == target else -1