- runs in $O(log(n))$ time & $O(1)$ space in the worst case, where $n$ is the size of the search space
- you can use it to
1. Find the index of $x$ if it is in $arr$
2. Find the first or last index where $x$ can be inserted to maintain sorted pattern
- search space has to be sorted
- whenever problem is sorted think about binary search
- [[Binary Search Trees]] are based on binary search
## General Algorithm
- if target exists, return its leftmost index
- else, returns the index of where it should be
- (note that where it should be might be out of bounds)
```
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
# do something
return
if arr[mid] > target:
right = mid - 1
else:
left = mid + 1
# target is not in arr, but left is at the insertion point
return left
```
```
def binary_search(nums, target):
l, r = 0, len(nums)
while l < r:
m = (l + r) // 2
if nums[m] < target:
l = m + 1
else:
r = m
return l
```
## Solution Space Problems
- we start by identifying the min possible answer & the max possible one
- if problem asks for the max or min of something that can be done, you potentially can use binary search if there is a threshold for what is possible & what isn't
- if below criteria are met you can use binary search:
1. You can quickly (in 𝑂(𝑛) or better) verify if the task is possible for a given number `x`.
2. If the task is possible for a number `x`, and you are looking for:
- A maximum, then it is also possible for all numbers less than `x`.
- A minimum, then it is also possible for all numbers greater than `x`.
3. If the task is not possible for a number `x`, and you are looking for:
- A maximum, then it is also impossible for all numbers greater than `x`.
- A minimum, then it is also impossible for all numbers less than `x`.
![[CleanShot 2024-06-03 at 14.21.22.png|400]]
- in most cases, algorithms that use this method are greedy ones
- we can also write a function check that takes an integer & checks if task is possible for that integer
## Important Templates
Binary Search Greedy Solution Space)
For Minimum: (problems where too little fails)
```
def fn(arr):
def check(x):
# this function is implemented depending on the problem
return BOOLEAN
left = MINIMUM_POSSIBLE_ANSWER
right = MAXIMUM_POSSIBLE_ANSWER
while left <= right:
mid = (left + right) // 2
if check(mid):
right = mid - 1
else:
left = mid + 1
return left
```
For Maximum: (problems where too much fails)
```
def fn(arr):
def check(x):
# this function is implemented depending on the problem
return BOOLEAN
left = MINIMUM_POSSIBLE_ANSWER
right = MAXIMUM_POSSIBLE_ANSWER
while left <= right:
mid = (left + right) // 2
if check(mid):
left = mid + 1
else:
right = mid - 1
return right
```
https://www.piratekingdom.com/leetcode/tricks/leftmost-binary-search