I was doing a problem in which we have to find kth smallest element using constant space and the array is read only. The array can be unsorted.

Link to the problem : https://www.interviewbit.com/problems/kth-smallest-element-in-the-array/

I want to know how the binary search solution works here.

Here is a working code I found:

```
int Solution::kthsmallest(const vector<int> &A, int B)
{
int maximum = 0;
for(int a : A) maximum = max(maximum, a);
int low = 0, high = maximum;
while(low != high)
{
int mid = (low + high + 1)/2;
int count = 0;
for(int a : A)
{
if(a < mid) count++;
}
if(count < B) low = mid;
else high = mid - 1;
}
return low;
}
```

what about https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/ ?

I was looking for the solution which involves binary search. Also, the array is read only and our solution should use constant space.Thanks,btw.

Tip: don't think binary search is just a "neat trick" that is useful on arrays from the input that you can sort. You can also apply binary search when there are no obvious arrays.

Let

`f(x)`

be the number of numbers in the given array that are smaller than`x`

. You can calculate`f(x)`

by just going through each element of the array. You can notice that if`x < y`

, than`f(x) <= f(y)`

. Why is this true? Well, all the numbers that are smaller than`x`

are also smaller than`y`

and`f(y)`

will also take into consideration the elements that are >=`x`

and smaller than`y`

, if they exist. Since`f(x) <= f(y)`

for any numbers`x`

and`y`

, such that`x < y`

,`f`

is increasing.Now, you can think of this function

`f`

as an increasing array and we need to find the index`i`

where we have`f(i) = k`

(or the smallest`i`

such that`f(i) > k`

, in case there is no`f(i) = k`

). As you can see, we basically now have a usual binary search problem. However, we are not done yet. It is not practical to calculate every single value of`f`

, because the binary search doesn't need all of them. You just need to calculate`f(mid)`

, where`mid`

is the middle position used in the binary search.In fact, you can use binary search on any increasing (or decreasing) function.

Got it.Thank you.