Leetcode (Algorithm I): 5. Search Insert Position

思路

也是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;
    }
};

但我

解释不清楚为什麽是回传lb...