What is Binary Search?
Binary search is a search algorithm that divides the search interval by half every time. That also means that the time complexity of binary search is O(log n)
Templates
Binary search can:
- find single element in a sorted array
- find first index satisfying a condition
Find single element in a sorted array
def binary_search(arr, target):
left, right = 1, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] < target:
left = mid + 1
elif arr[mid] > target:
right = mid - 1
else:
return mid
return -1
Find first index satisfying a condition
Finding the first index satisfying a condition is the same as finding the first true value of a true-false array.
ex: [False, ... False, True, ... True]
Things to note:
- left and right should include and read & write space
- while loop halts when
left == right
- after the while loop:
-
left
is the first index satisfyingcondition() == True
-
left - 1
is the last index satisfyingcondition() == False
-
def condition():
pass
def binary_search(arr):
left, right = 1, len(arr)-1
while left < right:
mid = (left + right) // 2
if condition():
right = mid
else:
left = mid + 1
return left
Top comments (0)