搜索插入位置-35

Given a sorted array of distinct integers 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 must write an algorithm with O(log n) runtime complexity.

示例 1：

Input: nums = [1,3,5,6], target = 5
Output: 2

示例 2：

Input: nums = [1,3,5,6], target = 2
Output: 1

示例 3：

Input: nums = [1,3,5,6], target = 7
Output: 4

示例 4：

Input: nums = [1,3,5,6], target = 0
Output: 0

示例 5：

Input: nums = [1], target = 0
Output: 0

提示：

• 1 ≤ nums.length ≤ 10；
• -10 ≤ nums[i] 10；
• nums contains distinct values sorted in ascending order.
• -10 ≤ target ≤ 10

思路

题目要求在O(log n)的时间复杂度下找到给定值的下表，这是一个二分查找的题目。

二分查找有两个编码思路：

• 第一个是Cpp代码所展示的。我们定义的搜索空间是[left, right]左闭右闭区间，注意我们的while(left <= right)且right = mid - 1;；
• 第二个是Rust代码锁展示的。我们定义的搜索空间是[left, right)左闭右开区间，注意我们的whilie(left < right)且right = mid;；

代码

Cpp：

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if( nums.size() == 1 ) {
            if( target > nums[0] )   return 1;
            return 0;
        }
        int left = 0, right = nums.size() - 1;
        while( right >= left ) {
            int mid = left + (right - left) / 2;
            if( nums[mid] == target )   
                return mid;
            else if( nums[mid] < target )
                left = mid + 1;
            else
                right = mid - 1;
        }
        // Target not found, insert it
        return left; 
    }
};

Rust：

impl Solution {
    pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
        if nums.len() == 1 {
            if target > nums[0] {
                return 1;
            }
            return 0;
        }
        let mut left = 0; 
        let mut right = nums.len();
        while right > left {
            let mut mid = left + (right - left) / 2;
            if nums[mid] > target { right = mid; }
            else if nums[mid] < target { left = mid + 1; }
            else { return mid as i32; }
        }
        // Target not found, insert it 
        left as i32
    }
}