博客

题目描述

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

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

示例 1:

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

输出: 2

示例 2:

输入: [1,3,5,6], 2

输出: 1

这道题相对来说较简单，没有太多难理解的点，所以我们直接实现。

代码实现：

三种方式实现

class Solution:
    '''
    搜索插入位置
    '''
    def searchInsert(self, nums, target):
        '''
        从头开始遍历查找,查找过程存在两种情况：
            1. 目标值与数组元素相等，或者目标值小于数组元素，返回数组元素索引
            2. 目标值大于数组最后一个元素值，返回最后一个索引+1，返回数组长度也行
        :param nums: 排序数组
        :param target: 查找的目标值
        :return: 目标值排序数组中的索引
        '''
        for i in range(len(nums)):
            if target <= nums[i]:
                return i
        return i+1



    def searchInsert_1(self, nums, target):
        '''
        指针指向的方式，查找过程存在两种情况：
            1. 数组中不存在目标值的情况：目标值大于数组元素时，指针递增，指向下一个元素，直到目标值小于数组元素时，返回指针init_n
            2. 数组中存在目标值的情况：目标值与数组元素相同时，返回指针init_n
        :param nums: 排序数组
        :param target: 查找的目标值
        :return: 目标值排序数组中的索引
        '''
        init_n = 0
        for i in range(len(nums)):
            if target > nums[i]:
                init_n +=1
        return init_n



    def searchInsert_2(self, nums, target):
        '''
        采用二分查找的方式实现
        :param nums: 排序数组
        :param target: 查找的目标值
        :return: 目标值排序数组中的索引
        '''
        start = 0
        end = len(nums) - 1
        while start <= end:
            mid = (start + end) // 2
            if nums[mid] > target:
                end = mid - 1
            elif nums[mid] < target:
                start = mid + 1
            else:
                return mid
        return start


li = [1,3,5]
num =0
result = Solution().searchInsert(li,num)
print(result)