Search Insert Position

标签： C++ 算法 LeetCode 数组 二分查找

每日算法——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) {
        
    }
};

翻译

查找插入位置

难度系数：中等

给定一个有序数组和一个目标值，如果数组中能找到此目标则返回索引。如果不能，返回它应该被插入的位置的索引。

假设数组中没有重复项。

以下是一些示例。

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

思路

相当于标准库std::lower_bound的实现

跟前面一个题类似， 只不过binarySearch没有找到不能返回-1， 而是返回low 或者high

代码

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

// 二分法实现
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;
    }
};