Hero Image
Binary Search 中的 lower bound & upper bound

前言

c++ 的 STL 有提供兩個跟 binary seach 有關的 function: lower_bound 和 upper_bound, 每次在寫 leetcode 相關的題目時都會一直忘記這兩個 function 的定義，故決定紀錄一下兩者的定義及用法

Include STL

lower_bound 和 upper_bound 被定義在 <algorithm> 裡面

#include <algorithm>

Lower Bound

找出數列中第一個 大於或等於 target 的位置, 換句話說就是找到 >= target 的最小值的位置

// vector<int> v;
// assume v is a sorted array
auto it = lower_bound(v.begin(), v.end(), target);
int idx = it - v.begin();

Upper Bound

找出數列中第一個 大於 target 的位置, 換句話說就是找到 > target 的最小值的位置

// vector<int> v;
// assume v is a sorted array
auto it = upper_bound(v.begin(), v.end(), target) - v.begin();
int idx = it - v.begin();

lower_bound 和 upper_bound 都會回傳 對應型態的 iterator, 如果傳入的 sequence 找不到目標值，就會回傳 v.end()

Monday, July 24, 2023 | 1 閱讀
Hero Image
LeetCode 隨筆 - 74. Search a 2D Matrix

題目難度：Medium

題目連結: Search a 2D Matrix

題目大綱

給你一個 m x n 的整數二維陣列和一個 value target，要你判斷 target 是否在這個陣列中。 題目保證這個二維陣列：

  1. 每個 row 的數字的順序已經由小到大排序過了
  2. 每個 row 的第一個數字一定比上一個 row 的最後一個數字還要大

解題思路

由題目可知，將這個二維陣列按照 row 展開成一維陣列後就是一個排序過的 array，所以我們就可以直接用 二分搜 (Binary Search) 來找 target。 需要注意的是傳入的是二維陣列，所以在寫 binary search 的時候需要轉換一維 & 二維之間的坐標系

一維 & 二維坐標系轉換範例： 假設我們要轉換一維陣列的 index i 到一個 m x n (m rows * n columns) 的二維陣列的 index (row, col)

row = i / n;
col = i % n;

程式碼

binary search 可以使用迴圈或遞迴的方式來實作，以下提供兩種版本供讀者參考

迴圈版

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();

        int left = 0, right = m*n - 1;
        int i, j, mid;

        while (left <= right) {
            mid = (left + right) / 2;
            i = mid / n;
            j = mid % n;
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }
};

遞迴版

class Solution {
public:
    int m, n;
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        m = matrix.size();
        n = matrix[0].size();
        return binarySearch(matrix, target, 0, m*n - 1);
    }

    bool binarySearch(vector<vector<int>>& matrix, int target, int begin, int end) {
        int mid;
        int i, j;

        if (begin > end)
            return false;

        mid = (begin + end) / 2;
        i = mid / n;
        j = mid % n;

        if (matrix[i][j] == target) {
            return true;
        } else if (matrix[i][j] > target) {
            return binarySearch(matrix, target, begin, mid-1);
        } else {
            return binarySearch(matrix, target, mid+1, end);
        }
    }
};

Saturday, June 18, 2022 | 2 閱讀