Intro to Binary search↵
==================↵
Given a sorted array $arr$ and a target number $k$, search for $k$ in $arr$.↵
↵
↵
↵
↵
### Naive approach↵
↵
Iterate over all $arr$ which would lead to $O(n)$ time complexity.↵
↵
### Binary search approach↵
↵
If we were at index $i$ and $arr[i] > k$ , then there is no need to check for all $j$ such that $j > i$ ( every index that comes after $i$ ) since $arr[j] > arr[i]$↵
therefore we can ignore every index greater than $i$ ( right side ) and update the search space.↵
↵
↵
If we were at index $i$ and $arr[i] < k$, then there is no need to check for all $j$ such that $j < i$ ( every index that comes before $i$ ) since $arr[j] < arr[i]$ therefore we can ignore every index less than $i$ ( left side ) and update the search space.↵
↵
If we were at the middle of the array search space then after one comparison, half of the array search space will be ignored, thus after each comparison, the current search space will be divided by two, which concludes a searching algorithm with complexity of $O( log(n) )$ since we are dividing the search space by 2 each comparison.↵
↵
↵
```cpp↵
int lb = 0 , ub = size - 1 ; //initializing the search space↵
while( lb <= ub ){↵
int mid = lb + (ub - lb)/2 ;// the middle position of the search space↵
↵
//dividing the search space by 2 ↵
if(arr[mid] > k ) ub = mid - 1 ;// ignoring the right side of mid and update the search space↵
else if( arr[mid] < k ) lb = mid + 1 // ignoring the left side of mid and update the search space↵
else break ; // we found the element ↵
}↵
```↵
↵
↵
↵
↵
Fun fact that any logarithmic function grows slower than polynomial. $O( log(n) )$ is better than $O( n^{0.000001}) )$ ↵
[for more info](https://www.reddit.com/r/askmath/comments/103utt/logarithmic_growth_versus_polynomial_growth/)↵
↵
Monotonic function↵
------------------↵
↵
$arr$ = ${1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 }$ and $k = 5$↵
↵
↵
Define a function $f(x)$ where x is an integer input and ↵
↵
$$ f(x)= \left\{↵
\begin{array}{ll}↵
1& x>= k \\↵
0& x < k\\↵
\end{array} ↵
\right. $$ ↵
↵
The output of the function when inputting $arr$, will always be some **zeros** then some **ones** like this↵
$0,0,0,0,1,1,1,1,1$↵
↵
↵
Since the array is sorted, numbers less than $k$ will be on the left and numbers greater than or equal $k$ will be on the right.↵
↵
So if you want to find the **first index** $i$ such that $arr[i] >= k$ then it will be the **first occurrence** of $1$ in $f(x)$ which will be at index $i = 5$ ( since $k = 5$ ) ↵
↵
↵
And if you want to find **last index** $i$ such that $arr[i] < k $ then it will be the **last occurrence** of $0$ in $f(x)$ which will be at index $i = 4$↵
↵
A provided built in function in c++.↵
↵
↵
```cpp↵
//the arr should be sorted!!↵
lower_bound(arr,arr+n , target) - arr // will binary search for the first index such that arr[i] >= target↵
upper_bound(arr,arr+n , target) - arr //will binary search for the first index such that arr[i] > target↵
```↵
↵
both return the **address** of the target element so subtracting the **address of the first element** will give us its **0-based index**↵
↵
↵
And if not found it returns the address of ```end```, ```end``` address is ```arr + n ```↵
↵
↵
The ```lower_bound``` will give us the **first** occurrence of ```1``` , to find the **last** occurrence of ```0``` we can **decrement the outputted index**↵
↵
↵
when using a ```vector``` its sufficient to replace ```arr``` with ```vector.begin()``` and ```arr+n``` with ```vector.end()``` ↵
↵
A monotonic function is a function that contain a block of ```zeros``` **then** a block of ```ones``` or the opposite.↵
↵
↵
it cant have mixed blocks , example : **000011110000111100001111** since standing at some value wont give enough data to cancel a side ↵
↵
### Classic problem : ↵
↵
output the number of elements in $arr$ between the range $L-R$ **(inclusive)**↵
↵
$L = 2$ , $R = 5$ and $arr = 1 , 1 , 2 , 2 , 3 , 4 , 5 ,5 ,5 ,6 , 9 ,10$↵
↵
↵
We can basically find the **first** index $i$ such that $arr[i] >= L$ , using ```lower_bound()``` ,name it $First$ ↵
↵
And **first** index $i$ such that $arr[i] > R$, using ```upper_bound()``` , name it $Last$ ↵
↵
After getting $First$ , $Last$ indices we can decrement the $Last$ index to get the **last index** such that $arr[i] <= R$↵
↵
$ANS = Last - First + 1$↵
↵
In the given example $First = 2$ , $Last = 8$ , $ANS = 8 - 2 + 1 = 7$↵
↵
↵
Binary search on answer↵
------------------↵
The [!Hasan problem link](https://mirror.codeforces.com/problemset/gymProblem/101257/D) ↵
↵
Given integers ```x``` and ```y``` ,where ```x``` is the **time needed for person1** to complete the setup for **a single** pc and ```y``` is the **time needed for person2** to complete the setup for **a single** pc.↵
↵
given ```n``` Pcs to setup , what is the minimum time needed to setup ```n``` Pcs , given that both person can work **simultaneously**.↵
↵
↵
Instead of finding an answer directly we can try out all the different times $t$ and take the minimum among them, doing it lineary is $O(t)$ where $t<=10^{18}$ , which is too slow.↵
↵
A good observation you can come up with is that if you can build $n$ pcs at time $t$ then at any further time you can still build the $n$ pcs, which concludes to a monotonic function .↵
↵
Define the following function $f(t)$, where $t$ is the time taken . the function outputs $1$ when you can build **more than or equal** to $n$ pcs , and $0$ otherwise ↵
the total number of pcs you can build at time $t$ is $(t/x + t/y)$ , name it built.↵
↵
$$ f(t)= \left\{↵
\begin{array}{ll}↵
1& built >= n \\↵
0& built< n \\↵
\end{array} ↵
\right. $$ ↵
↵
Thus the output of the monotonic function will be a block of **zeros** then a block of **ones** , $00...0011...11$ ↵
↵
The **first** occurrence of **1** will get us the **minimum time** needed .↵
↵
↵
<spoiler summary="Solution">↵
```cpp↵
bool f(int t , int x , int y, int n){↵
int built = t/x + t/y ;↵
return built >= n ;↵
}↵
↵
int n , x , y ; cin >> n >> x >> y ;↵
↵
int lb = 0,ub = min(x,y)*n ;// a reasonable upper bound since that's the time needed for one person to finish n pcs↵
int ans = -1 ;↵
while( lb <= ub){↵
int mid = lb + (ub-lb)/2 ; ↵
↵
// incase the function outputs a one , i will save the current time and search for an earlier time ↵
if(f(mid,x,y,n)) ans = mid , ub = mid - 1 ; // update the search space and ignore everything greater than mid ↵
else lb = mid+1 ;//incase the function outputs zero , update the search space and ignore everything less than mid ↵
↵
}↵
↵
↵
cout << ans << endl;↵
↵
```↵
</spoiler>↵
↵
↵
==================↵
Given a sorted array $arr$ and a target number $k$, search for $k$ in $arr$.↵
↵
↵
↵
↵
### Naive approach↵
↵
Iterate over all $arr$ which would lead to $O(n)$ time complexity.↵
↵
### Binary search approach↵
↵
If we were at index $i$ and $arr[i] > k$ , then there is no need to check for all $j$ such that $j > i$ ( every index that comes after $i$ ) since $arr[j] > arr[i]$↵
therefore we can ignore every index greater than $i$ ( right side ) and update the search space.↵
↵
↵
If we were at index $i$ and $arr[i] < k$, then there is no need to check for all $j$ such that $j < i$ ( every index that comes before $i$ ) since $arr[j] < arr[i]$ therefore we can ignore every index less than $i$ ( left side ) and update the search space.↵
↵
If we were at the middle of the array search space then after one comparison, half of the array search space will be ignored, thus after each comparison, the current search space will be divided by two, which concludes a searching algorithm with complexity of $O( log(n) )$ since we are dividing the search space by 2 each comparison.↵
↵
↵
```cpp↵
int lb = 0 , ub = size - 1 ; //initializing the search space↵
while( lb <= ub ){↵
int mid = lb + (ub - lb)/2 ;// the middle position of the search space↵
↵
//dividing the search space by 2 ↵
if(arr[mid] > k ) ub = mid - 1 ;// ignoring the right side of mid and update the search space↵
else if( arr[mid] < k ) lb = mid + 1 // ignoring the left side of mid and update the search space↵
else break ; // we found the element ↵
}↵
```↵
↵
↵
↵
↵
Fun fact that any logarithmic function grows slower than polynomial. $O( log(n) )$ is better than $O( n^{0.000001}) )$ ↵
[for more info](https://www.reddit.com/r/askmath/comments/103utt/logarithmic_growth_versus_polynomial_growth/)↵
↵
Monotonic function↵
------------------↵
↵
$arr$ = ${1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 }$ and $k = 5$↵
↵
↵
Define a function $f(x)$ where x is an integer input and ↵
↵
$$ f(x)= \left\{↵
\begin{array}{ll}↵
1& x>= k \\↵
0& x < k\\↵
\end{array} ↵
\right. $$ ↵
↵
The output of the function when inputting $arr$, will always be some **zeros** then some **ones** like this↵
$0,0,0,0,1,1,1,1,1$↵
↵
↵
Since the array is sorted, numbers less than $k$ will be on the left and numbers greater than or equal $k$ will be on the right.↵
↵
So if you want to find the **first index** $i$ such that $arr[i] >= k$ then it will be the **first occurrence** of $1$ in $f(x)$ which will be at index $i = 5$ ( since $k = 5$ ) ↵
↵
↵
And if you want to find **last index** $i$ such that $arr[i] < k $ then it will be the **last occurrence** of $0$ in $f(x)$ which will be at index $i = 4$↵
↵
A provided built in function in c++.↵
↵
↵
```cpp↵
//the arr should be sorted!!↵
lower_bound(arr,arr+n , target) - arr // will binary search for the first index such that arr[i] >= target↵
upper_bound(arr,arr+n , target) - arr //will binary search for the first index such that arr[i] > target↵
```↵
↵
both return the **address** of the target element so subtracting the **address of the first element** will give us its **0-based index**↵
↵
↵
And if not found it returns the address of ```end```, ```end``` address is ```arr + n ```↵
↵
↵
The ```lower_bound``` will give us the **first** occurrence of ```1``` , to find the **last** occurrence of ```0``` we can **decrement the outputted index**↵
↵
↵
when using a ```vector``` its sufficient to replace ```arr``` with ```vector.begin()``` and ```arr+n``` with ```vector.end()``` ↵
↵
A monotonic function is a function that contain a block of ```zeros``` **then** a block of ```ones``` or the opposite.↵
↵
↵
it cant have mixed blocks , example : **000011110000111100001111** since standing at some value wont give enough data to cancel a side ↵
↵
### Classic problem : ↵
↵
output the number of elements in $arr$ between the range $L-R$ **(inclusive)**↵
↵
$L = 2$ , $R = 5$ and $arr = 1 , 1 , 2 , 2 , 3 , 4 , 5 ,5 ,5 ,6 , 9 ,10$↵
↵
↵
We can basically find the **first** index $i$ such that $arr[i] >= L$ , using ```lower_bound()``` ,name it $First$ ↵
↵
And **first** index $i$ such that $arr[i] > R$, using ```upper_bound()``` , name it $Last$ ↵
↵
After getting $First$ , $Last$ indices we can decrement the $Last$ index to get the **last index** such that $arr[i] <= R$↵
↵
$ANS = Last - First + 1$↵
↵
In the given example $First = 2$ , $Last = 8$ , $ANS = 8 - 2 + 1 = 7$↵
↵
↵
Binary search on answer↵
------------------↵
The [!Hasan problem link](https://mirror.codeforces.com/problemset/gymProblem/101257/D) ↵
↵
Given integers ```x``` and ```y``` ,where ```x``` is the **time needed for person1** to complete the setup for **a single** pc and ```y``` is the **time needed for person2** to complete the setup for **a single** pc.↵
↵
given ```n``` Pcs to setup , what is the minimum time needed to setup ```n``` Pcs , given that both person can work **simultaneously**.↵
↵
↵
Instead of finding an answer directly we can try out all the different times $t$ and take the minimum among them, doing it lineary is $O(t)$ where $t<=10^{18}$ , which is too slow.↵
↵
A good observation you can come up with is that if you can build $n$ pcs at time $t$ then at any further time you can still build the $n$ pcs, which concludes to a monotonic function .↵
↵
Define the following function $f(t)$, where $t$ is the time taken . the function outputs $1$ when you can build **more than or equal** to $n$ pcs , and $0$ otherwise ↵
the total number of pcs you can build at time $t$ is $(t/x + t/y)$ , name it built.↵
↵
$$ f(t)= \left\{↵
\begin{array}{ll}↵
1& built >= n \\↵
0& built< n \\↵
\end{array} ↵
\right. $$ ↵
↵
Thus the output of the monotonic function will be a block of **zeros** then a block of **ones** , $00...0011...11$ ↵
↵
The **first** occurrence of **1** will get us the **minimum time** needed .↵
↵
↵
<spoiler summary="Solution">↵
```cpp↵
bool f(int t , int x , int y, int n){↵
int built = t/x + t/y ;↵
return built >= n ;↵
}↵
↵
int n , x , y ; cin >> n >> x >> y ;↵
↵
int lb = 0,ub = min(x,y)*n ;// a reasonable upper bound since that's the time needed for one person to finish n pcs↵
int ans = -1 ;↵
while( lb <= ub){↵
int mid = lb + (ub-lb)/2 ; ↵
↵
// incase the function outputs a one , i will save the current time and search for an earlier time ↵
if(f(mid,x,y,n)) ans = mid , ub = mid - 1 ; // update the search space and ignore everything greater than mid ↵
else lb = mid+1 ;//incase the function outputs zero , update the search space and ignore everything less than mid ↵
↵
}↵
↵
↵
cout << ans << endl;↵
↵
```↵
</spoiler>↵
↵
↵
