BS

[sync-by-unito[bot]]

Binary Search Pattern: //https://leetcode.com/explore/learn/card/binary-search/136/template-analysis/935/

//33. Search in Rotated Sorted Array [Med] //1428. Leftmost Column with at Least a One [Med]

    int binarySearch(BinaryMatrix &b, int rn, int col){
        int lo = 0, hi = col-1;
        while(lo <= hi){
            int med = lo + (hi-lo)/2;
            if(b.get(rn, med) == 1){
                hi = med-1;
            }else{
                lo = med+1;
            }
        }
        return (lo == col)? -1 : lo;
    }

┆Issue is synchronized with this Trello card by Unito

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//33. Search in Rotated Sorted Array [Med]

class Solution_q33_b { public: //https://leetcode.com/problems/search-in-rotated-sorted-array/discuss/14435/Clever-idea-making-it-simple //https://leetcode.wang/leetCode-33-Search-in-Rotated-Sorted-Array.html int search(std::vector& nums, int target) { int lo = 0, hi = nums.size() - 1; while (lo <= hi) { int mid = (lo + hi) / 2; if (target == nums[mid]) return mid;

        //if nums[lo..mid] are accessdending, means pivot is not in this section.
        if (nums[lo] <= nums[mid]) {
            if (nums[lo] <= target && target < nums[mid])
                hi = mid - 1;
            else
                lo = mid + 1;
        }
        else {
            if (nums[mid] < target && target <= nums[hi])
                lo = mid + 1;
            else
                hi = mid - 1;
        }
    }
    return -1;
}

};

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//1428. Leftmost Column with at Least a One

class Solution { public: //https://leetcode.com/explore/learn/card/binary-search/136/template-analysis/935/ int binarySearch(BinaryMatrix &b, int rn, int col){ int lo = 0, hi = col-1; while(lo <= hi){ int med = lo + (hi-lo)/2; if(b.get(rn, med) == 1){ hi = med-1; }else{ lo = med+1; } } return (lo == col)? -1 : lo; } int leftMostColumnWithOne(BinaryMatrix &mat) { // Step 1. get the dimensions int row = mat.dimensions()[0]; int col = mat.dimensions()[1];

    // Step 2. get the first 1's index for each row, if there is no 1, record it as -1;
    vector<int> v (row, -1);
    for(int r=0; r<row; r++){
        v[r] = binarySearch(mat, r, col);
        //cout << "row: " << r << ",idx:" << v[r] << endl;
    }

    // Step 3. Sort it and return result
    std::sort(v.begin(), v.end());
    v.erase(std::remove(v.begin(), v.end(), -1), v.end());
    return v.empty()? -1 : v[0];
}

};