#704. Binary Search | LeetCode Python Solution
Problem
LeetCode Problem
- Binary Search
Python Solution
class Solution:
def search(self, nums: List[int], target: int) -> int:
# Initialize start and end index
start, end = 0, len(nums)-1
# Iterate when start index is less than end index
while start < end:
mid = math.floor((start + end) / 2)
# Target found so return immediately
if target == nums[mid]:
return mid
# Target might be on the left side
elif target < nums[mid]:
end = mid - 1
# Target might be on the right side
else:
start = mid + 1
# When start and end index meet, return the index if it's the target
if start == end and nums[start] == target:
return start
else:
return -1
""" Test Data
Input: nums = [2], target = 0
Input: nums = [2], target = 2
Input: nums = [2,5], target = 0
Iteration 1: start = 0, end = 1, mid = 0, nums[mid] = 2 => start = 0, end = 0
Input: nums = [2,5], target = 2
Iteration 1: start = 0, end = 1, mid = 0, nums[mid] = 2
Input: nums = [2,5], target = 5
Iteration 1: start = 0, end = 1, mid = 0, nums[mid] = 2 => start = 1, end = 1
Input: nums = [-1,0,3,5,9,12], target = 9
idxs = [ 0,1,2,3,4, 5]
Iteration 1: start = 0, end = 5, mid = 2, nums[mid] = 3 => start = 3, end = 5
Iteration 2: start = 3, end = 5, mid = 4, nums[mid] = 9
Input: nums = [-1,0,3,5,9,12], target = 2
idxs = [ 0,1,2,3,4, 5]
Iteration 1: start = 0, end = 5, mid = 2, nums[mid] = 3 => start = 0, end = 1
Iteration 2: start = 0, end = 1, mid = 0, nums[mid] = -1 => start = 1, end = 1
Input: nums = [-1,0,3,5,9,12], target = -100
idxs = [ 0,1,2,3,4, 5]
Iteration 1: start = 0, end = 5, mid = 2, nums[mid] = 3 => start = 0, end = 1
Iteration 2: start = 0, end = 1, mid = 0, nums[mid] = 0 => start = 0, end = -1
Input: nums = [-1,0,3,5,9,12], target = 13
idxs = [ 0,1,2,3,4, 5]
Iteration 1: start = 0, end = 5, mid = 2, nums[mid] = 3 => start = 3, end = 5
Iteration 2: start = 3, end = 5, mid = 4, nums[mid] = 9 => start = 4, end = 5
Iteration 2: start = 4, end = 5, mid = 4, nums[mid] = 9 => start = 5, end = 5
"""