52ms Binary Search in C++


  • 1
    A
    class Solution {
    public:
        int kthSmallest(vector<vector<int>>& matrix, int k) {
            int n = matrix.size();
            if(n == 0) return -1;
            int minval = matrix[0][0] , maxval = matrix[n - 1][n - 1], mid;
            while(minval < maxval)
            {
                mid = minval + ((maxval - minval) >> 1);//find the middle value of the range between maxval and minval
                int count = 0, j = n - 1;
                for(int i = 0; i < n && matrix[i][0] <= mid; i++)//count how many number of elements in the matrix less than middle value. 
                {
                    while(j >= 0 && matrix[i][j] > mid) j--;
                    count += j + 1;
                }
                if(count < k)
                minval = mid + 1;
                else
                maxval = mid;
            }
            return minval;
        }
    };
    

    just think this matrix as a range of [minval maxval]. Every time we find the middle value in this range, and count how many number in the matrix less than the middle value.Finally, we renew the range base on count number.


  • 0

    I can't understand how it works, Could you explain in detail?


  • 0
    A

    @LinHungShi just think this matrix as a range of [minval maxval]. Every time we find the middle value in this range, and count how many number in the matrix less than the middle value.Finally, we renew the range base on count number.


  • 0
    A
    This post is deleted!

  • 1
    T

    I'm failing to see how this finds the midpoint. in binary search the midpoint is the value whose index is at the middle of the array. in your program it looks like you're trying to find the midpoint of the actual values, which may not even be in the array.

    In other words, if the array is:

    [0, 99, 100]

    the midpoint is (0 + 2)/2 = 1

    but in your code you're calculating

    (0 + 100)/2 = 50.

    please correct me. this was accepted so it must be right but im not seeing how this works.


  • 0
    A

    @tambourine Yes, you are right.This "Binary Search" isn't like the standard Binary Search, which middle point is the middle point of the range rather than the middle of index.


  • 0
    X

    How are you sure that the minval is in the matrix? I mean I get it that there will be exactly k elements smaller than mid. But how are you sure that value is an element of the matrix?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.