O(lg(m) + lg(n)) C++ binary search


  • 0
    G

    First, find the row which might have the target. This is the same as "Search Insert Position": the position minus one is the row number;

    Second, find the target in this row.

    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            int n = matrix.size();
            int m = matrix[0].size();
            int l = 0, r = n - 1, k;
            
            if (target < matrix[0][0]) {           //If the target is less than the first element, abort immediately.
                return false;
            }
            
            while (l <= r) {
                k = l + ((r - l) >> 1);
                if (matrix[k][0] > target) {
                    r = k - 1;
                } else if (matrix[k][0] < target) {
                    l = k + 1;
                } else {
                    return true;
                }
            }
            k = l + ((r - l + 1) >> 1) - 1;         //The inserting position minus one: the row which might have the target
            int mid;
            l = 0; r = m - 1;
            while (l <= r) {
                mid = l + ((r - l) >> 1);
                if (matrix[k][mid] > target) {
                    r = mid - 1;
                } else if (matrix[k][mid] < target) {
                    l = mid + 1;
                } else {
                    return true;
                }
            }
            return false;
        }
    };

  • 0
    M

    can you please explain k=l+((r-l+1)>>1)-1;


  • 0
    G

    (l+r+1)/2 - 1


  • 0
    M

    i tried
    k= (l+r)>>1;
    my code was accepted


Log in to reply
 

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