Binary Search — Basic Concepts
Including Algorithm Introduction And Three Useful Templates
Binary search is an algorithm that speeds up to find a target in an ordered list, its time complexity is O(logN) whilst a normal linear search is O(n).
But how does it works?
The three main elements we need are a left index, a right index and a middle index, and each time we divided our list in half until we find the target. Due to every time we search, we cut half of the list that we no longer need to consider, the time complexity can be reduced into O(logN).
Binary Search Algorithm
- Calculate the middle index and get the middle value
- Comparing the target value with the middle value, if the middle value is equal to the target, then we found it and the function can be stopped
- If the middle is less than the target, it means the target is on the right and we want to search the right half of the list. Move the left index to the middle index plus one to shorten the range to the right half
- Conversely, if the middle is greater than the target, then we search the left half of the list to find the target. Move the right index to the middle index minus one, reducing the extent of the list to the left half
- Repeat steps 2, 3, and 4 until the middle value is equal to the target, otherwise, it means the target value does not exist in the list
Binary Search Template
Every time we encounter a binary search problem, you might find out the solution code is different each time, and it is because the conditions are slightly different from each question. It could be really annoying and confusing.
So here, I listed three basic and useful templates that every time you face a binary search problem, you can start with these templates first and then make minor changes according to the problem conditions.
[Notice] If the number in nums is not sorted, remember to sort it first.
template 1
def binarySearch(nums, target):
if len(nums) == 0:
return -1
left, right = 0, len(nums) - 1
# End Condition: left > right
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1template 2
def binarySearch(nums, target):
if len(nums) == 0:
return -1
left, right = 0, len(nums) - 1
# End Condition: left == right
while left < right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid
# Post-processing (process the remaining data)
if nums[left] == target:
return left
return -1template 3
def binarySearch(nums, target):
if len(nums) == 0:
return -1
left, right = 0, len(nums) - 1
# End Condition: left + 1 == right
while left + 1 < right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid
else:
right = mid
# Post-processing (process the remaining data)
if nums[left] == target:
return left
if nums[right] == target:
return right
return -1
