iamskp's blog

Kth smallest element (Binary Search)
By iamskp, history, 4 years ago, In English

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;
}
  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply