- 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