---
# System prepended metadata

title: Binary Search
tags: [Data Structures & Algorithms, GeeksforGeeks]

---

# 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

``` python
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

``` python
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)
``` python
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] 
```


``` python
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
``` python
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] 
```

``` python
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
``` python
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
``` python
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