Lecture_Notes/imperfect_notes/pragy/Binary Search 2.md

Binary Search 2
---------------

Median of two sorted arrays
---------------------------
- merge: O(n). Search O(log n) 
- binary search: O(log n)
- pick the smaller array
- low = 0, high = length of smaller array
- partition the other array so that number of elements in first of both = number of elements in last of both
- now check if this partition is valid by cross comparison
- change high and low accordingly
- append -inf and +inf to start and ends of arrays

Special Integer
-------------------------------------
> Unsorted array of size N.
> +ve numbers.
> Given X, find max value of K such that no subarray of length k has sum > x
- binary search over k in 0..N
- if any sum > X, k is not the answer
- if sum <= x, k might be the answer if k+1 is not allowed
- finding max sum for a given k takes O(n) time
- todo: change to m and not m-1/m+1 loop till h-l>1
-- --

Sorted array of length N.
-------------------------------------
> numbers are from 1..N-1 (so contiguous).
> One of the numbers is repeated.
> Find it

- 1 2 3 4 4 5 6 7 8  (number)
- 0 1 2 3 4 5 6 7 8  (index)
- N N N N Y Y Y Y Y  (proposition)

Agressive Cows
--------------

> N stalls, n >= 2
> C cows, c >= 2
> locations of stalls, let's say 1, 2, 5, 7, 8
> Maximize the minimum distance between any two cows

- low = 1
- high = N
- calculate mid = distance, and check

Smallest Good Base
------------------
> $N \in \{3, 10^{18}\}$
> k >= 2
> $(N)_k = 1111111\ldots$
> Find smallest k

- example: N = 7
    - k = 2, $(7)_2 = 111$
- finding the largest good base is trivial - N-1
- low = 2, high = n-1
- If $m$ is the answer, then $\exists i: 1 + m + m^2 + \cdots + m^i = N$
- But we still can't binary search since we don't know $i$. $i$ will change for different numbers
- Also, say we found a working or non working m. How do we change the low and high? Multiple possible answers, which one to chose?
- Let's look at it from searching on i
- We need to maximize i (thereby minimize k)
- $(7)_6 = 11, (7)_2 = 111$, we need to output 2.
- So, linear search over all possible number of bits from 63 to 2
    - Then for a fixed (i), binary search for the value of m (or use formula of geometric series)
- low, high for number of bits will be $1, \log_2 N$ (because smallest k is 2)
- $2^{63} \approx 10^{18}$


Smallest subarray
-----------------

> Array of length N
> Not sorted
> +ve numbers
> Find length of smallest subarray such that sum >= k
- calculate prefix sum (prefix sum is sorted)
- can you calculate sum a[i] .. a[j]?
    - a[i] .. a[j] = P[j] - P[i] + a[i]
- now, let's say the answer starts from S and ends at E
    - loop over all possible S
        - binary search for E
    - return S, E that has min distance

Election
--------

> N People
> influence[1..n]: 1 2 2 3 1    (+ve)
> Voting: ith person votes for jth person if sum(influence[i+1:j-1]) <= influence[i]
> Note: j can lie on the left side as well
> Print the array of votes each person got

- So, in 1 2 2 3 1, the number of people who can vote for a[i] are 2 3 2 3 3
- now, if we try to find how many people vote for i, it is linear search, so total $O(n^2)$
- instead, we can calculate prefix sum, and for each person, see what range of people it can vote for using binary search. So O(n \log n)
- Now that we have ranges, we need to find the final array
- O(n) algo to convert ranges to array by doing +1 on start, -1 on end, and then taking prefix sum