---
# System prepended metadata

title: Untitled

---

By applying binary search, we first find the middle element m by calculating the average of the upper bound and lower bound. 
• Compare the f(m) with V.

• Case 1 : Since f(x) is ascending, if f(m) is smaller than the V which means x must be between m+1 and the upper bound. So we set the new lower bound to m+1. 

• Case 2: Since f(x) is ascending, if f(m) is greater than or equal to  V and f(m-1) is also greater than or equal to  V which means x must be between lower bound and m-1. So we set the new upper bound to the m-1. 

• Case 3: If f(m) is greater than or equal to  V and f(m-1) is smaller than V, then return the m.

We search recursively until we meet case 3, during that time we keep tighter the bound. 

Complexity
While searching for the matching element, the searching interval is cut to half by taking the recursive step. Hence, we find the ideal fridge by using O(log V ) algorithm


-----------------
We use divide and conquer strategy, and the main idea is to apply the merge-sort algorithm.


We split the array A’ into two halves 〖A'〗_top=A'[1…⌊n/2⌋  and 〖A^'〗_bottom=A'[⌊n/2⌋+1…n], then divide array recursively into two sub-arrays until there is only single element in each sub-array. Next, we start recursively merging two arrays and count the inversion as the same time. We compare each element in left sub-array with each element in right sub-array, if the element in left sub-array is greater than the element right sub-array we increment the count of inversion. In the merge process, we take i to indexing left sub-array and j to indexing right sub-array. 


The total number of inversions I(A') = I(〖A'〗_top) + I(〖A^'〗_bottom) +I(〖A^'〗_(top )  ,〖A^'〗_bottom)