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] \gt k$$$ , then there is no need to check for all $$$j$$$ such that $$$j \gt i$$$ ( every index that comes after $$$i$$$ ) since $$$arr[j] \gt 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] \lt k$$$, then there is no need to check for all $$$j$$$ such that $$$j \lt i$$$ ( every index that comes before $$$i$$$ ) since $$$arr[j] \lt 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.

  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

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

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] \gt = 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] \lt 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++.

//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] \gt = L$$$ , using lower_bound() ,name it $$$First$$$

And first index $$$i$$$ such that $$$arr[i] \gt 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] \lt = 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

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 \lt =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.

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 .

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;