標(biāo)簽： C++ 算法 LeetCode 數(shù)組 二分查找

每日算法——leetcode系列

問題 SeSearch Insert Position

Difficulty: Medium

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        
    }
};

翻譯

查找插入位置

難度系數(shù)：中等

給定一個有序數(shù)組和一個目標(biāo)值，如果數(shù)組中能找到此目標(biāo)則返回索引。如果不能，返回它應(yīng)該被插入的位置的索引。

假設(shè)數(shù)組中沒有重復(fù)項。

以下是一些示例。

[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

思路

相當(dāng)于標(biāo)準(zhǔn)庫std::lower_bound的實現(xiàn)

跟前面一個題類似， 只不過binarySearch沒有找到不能返回-1， 而是返回low 或者high

代碼

// 直接調(diào)用lower_bound
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
    }
};

// 二分法實現(xiàn)
class Solution {
public:
    int searchInsert(vector<int> &nums, int target) {
        if (nums.empty()){
            return 0;
        }
        int low = 0;
        int high = (int)(nums.size() - 1);
        return binarySearch(nums, low, high, target);
    }
    
private:
        
    int binarySearch(vector<int> nums, int low, int high, int target){
        
        while (low <= high) {
            int mid = low + (high - low)/2;
            if (nums[mid] == target) {
                return mid;
            }
            if (target > nums[mid]) {
                low = mid + 1;
            }
            if (target < nums[mid]) {
                high = mid - 1;
            }
        }
        return low;
    }
};