# Binary Search
- helps to find a target number inside a sorted array of numbers
- can be applied to lexicograpically sorted words in an array

Note: find mid using left + (right - left)//2 -> to avoid stackoverflow

Calculating mid
- m = (l + r) // 2
- m = l + ((r - l) // 2)

m = l + ((r - l) // 2) 
m = l + r // 2 - l //2 
m = l // 2 + r // 2 
m = (l + r) / 2

## Problems
- find the index of target element

def find_element(arr, target):
    l = 0
    r = len(arr) - 1
    while l <= r:
        m = l + ((r - l) // 2)
        if arr[m] == target:
            return m
        
        if arr[m] < target:
            l = m + 1
        else:
            r = m - 1
    return -1

- upper bound (ceil)
- find the first value that is greater than or equals to x

def find_celing(arr, target):
    l = 0
    r = len(arr) - 1
    possible_result = None
    while l <= r:
        m = l + ((r - l) // 2)
        if arr[m] >= target:
            possible_result = arr[m]
            r = m - 1
        else:
            l = m + 1
    return possible_result

- Lower bound (floor)

def find_floor(arr, target):
    l = 0
    r = len(arr) - 1
    possible_result = None
    while l <= r:
        m = l + ((r - l) // 2)
        if arr[m] <= target:
            possible_result = arr[m]
            l = m + 1
        else:
            r = m - 1
    return possible_result

- Find First and Last Position of Element in Sorted Array
- Find target value floor and ceiling and return

- Rotated Array (finding pivot point)
- somebody rotated (shifted) a sorted array. find the smallest element or find the rotation point
- variation of lower bound problem
Note:
- it only works if there are unique elements
- return first element as lowest if its not rotated

arr = [6, 7, 9, 15, 19, 2, 3] 
arr = [T, T, T, T, T, F, F] 

condition = val >= arr[0] 

arr = [6, 7, 9, 15, 19, 2, 3] 
l = 0
r = len(arr) - 1
# its not rotated return the first lement as lowest
result = arr[0] 
while l <= r:
    mid = l + (r - l) // 2
    current = arr[mid] >= arr[0]
    if not current:
        result = arr[mid]
        r = mid - 1
    else:
        l = mid + 1
return result 
       
- Search in roated array
    - find the pivot point
    - pivot point partitions the array (of length n) into two sorted portions nums[0 ~ pivot - 1] and nums[pivot ~ n - 1]
    - search in both partitions 


- Find Minimum in Rotated Sorted Array
    - find the pivot point and that would be the mininum
    - 

    

- Find peak
- array is increases and then decreases. find the maximum
- Intution value greater than the previous value
- Note: if more an one peak return any one

arr = [2, 3, 4, 6, 9, 12, 11, 8, 6, 4, 1]
arr = [T , T, T, T, T, T,  F,  F, F, F, F]

condition: m == 0 or arr[m - 1] < arr[m] 

arr = [2, 3, 4, 6, 9, 12, 11, 8, 6, 4, 1]
l = 0
r = len(arr) - 1
result = None
while l <= r:
    mid = l + (r - l)//2
    if mid == 0 or arr[mid - 1] < arr[mid]:
        result = mid
        l = mid + 1
    else:
        r = mid - 1
return result 

- binary search on real values

l = 0
r = x
step = 1 / (10 ** precision)
possible_ans = -1
while r - l > step:
    mid = l + (r - l) / 2
    current = mid * mid
    if current <= x:
        possible_ans = mid
        l = mid + step 
    else:
        r = mid - step
return round(possible_ans, precision)

Problems
- Group 1
- sqrt(x)
- find first value >= x (lower bound)
- Guess number higher or lower
- Search in rotated sorted array
- find the peak
- split the problem in to two binary search
- Group 2
- First bad version
- Find Peak element
- if array is increasing and decreasing
- Find minimum in rotated
- Group 3
- Search for Range
- Find K Closest elements
- Find peak element

- find an element in sorted array (distinct elements)
- complexity
- TC - O(log n)
- SC - O(1)
- Logic -> using binary search

sorted array
- asending or desending
- monotonic function -> single tone when plotted in graph

- find an element in sorted array (contains repeated elements pick the first or last occurance)
- complexity
- TC - O(log n)
- SC - O(1)
- Logic -> using modified binary search

- find the number of times the element present in sorted array
- complexity
- TC - O(log n)
- SC - O(1)
- Logic -> last occurance - first occurance + 1

- find the element present in sorted array or closest ??

- find the pivot index in right rotated sorted array ??
- eg [3, 4, 5, 6, 7, 1, 2]
- logic search for an element where mid is last or right is smaller than mid

- search and insert
- combined finding celing and target
- https://leetcode.com/problems/search-insert-position/description/?envType=study-plan-v2&envId=top-interview-150

nums = [1,3,5,6]
target = 2
output = 1

l = 0
r = len(nums) - 1
# important for -1 if no element in array it would default to 0th element 
result = -1
while l <= r:
    m = l + (r - l)//2
    if nums[m] == target:
        return m
    if nums[m] < target:
        result = m
        l = m + 1
    else:
        r = m - 1
# increment the celing by one
return result + 1

Reference
- [Binary search - various implementations - Kamil Dębowski - Youtube](https://www.youtube.com/watch?v=LcWPKR1uef4)
- [Binary search - summary - Kamil Dębowski - Youtube](https://www.youtube.com/watch?v=GU7DpgHINWQ&list=PLl0KD3g-oDOEbtmoKT5UWZ-0_JbyLnHPZ)
- Binary search Practice practice problems - https://leetcode.com/explore/learn/card/binary-search/138/background/971/
- Leetcode interview practice problems - https://leetcode.com/studyplan/top-interview-150/

33. Search in Rotated Sorted Array
1060. Missing Element in Sorted Array
1901. Find a Peak Element II
1231. Divide Chocolate
1182. Shortest Distance to Target Color