Leetcode (Algorithm I): 5. Search Insert Position

leetcode algorithm i

細枝 2022-01-04 23:38:03 ‧ 685 瀏覽

分享至

思路

也是binary search的應用題，承前兩篇文章，有lb跟ub和index三個數值可選，我目前覺得應該是回傳lower bound值。

程式

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int p = -1, f = 0;
        int lb = 0, ub = nums.size() - 1;
        while( ub >= lb ) {
            int index = lb + (ub - lb) / 2;
            if ( nums[index] < target ) 
                lb = index + 1;
            else if ( nums[index] > target )
                ub = index - 1;
            else {
                f = 1;
                p = index;
                break;
            }
            //cout << "(" << lb << ", " << ub << "," << index << ")";
        }
        if ( !f )
            p = lb;
        return p;
    }
};