题目

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5
输出: 2
示例 2:

输入: [1,3,5,6], 2
输出: 1
示例 3:

输入: [1,3,5,6], 7
输出: 4
示例 4:

输入: [1,3,5,6], 0
输出: 0

思路

方法一：利用二分法进行查找target
方法二：利用各个语言的内置函数，先插入在排序然后索引（这样做就失去了题目的意义了）

Rust实现

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

Go语言实现

func searchInsert(nums []int, target int) int {
	low := 0
	high := len(nums)
	for ;low<high; {
		mid := low + (high - low)/2
		if nums[mid] > target{
			high = mid
		} else if nums[mid] < target {
			low = mid + 1
		} else {
			return mid
		}
	}
	return low
}

Python实现

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        low = 0
        high = len(nums)
        while low < high:
            mid = int(low + (high - low)/2)
            if nums[mid] > target:
                high = mid
            elif nums[mid] < target:
                low = mid +1
            else:
                return mid
        return low
  

JavaScript实现

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let low = 0
    let high = nums.length
    while (low < high){
        let mid = parseInt(low + (high-low)/2)
        if (nums[mid] < target){
            low = mid +1
        } else if (nums[mid] > target){
            high = mid
        } else {
            return mid
        }
    }
    return low
};

结果

源码下载地址：

源码下载地址