leetcode | 35.搜索插入位置

35.搜索插入位置

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

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

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

题目链接

思路

1. 利用二分查找目标值，如果存在，返回其索引，如果不存在，寻找插入位置。
   （1）二分查找找到目标值，时间复杂度为O(log n)
   （2）二分查找没找到目标值，时间复杂度为O(log n) + O(n)
   因此，该方法会时间复杂度不符合题意。
2. 根据题意，找到大于等于目标值的位置，该位置即为插入位置/目标值的位置。
   该方法需要遍历数组，因此时间复杂度为O(n)，不符合题意。
3. 二分查找变形

   代码

   class Solution(object):
   	def searchInsert(self, nums, target):
   		"""
   		利用二分查找目标值，如果存在，返回其索引，如果不存在，寻找插入位置。
   		（1）二分查找找到目标值，时间复杂度为O(log n)
   		（2）二分查找没找到目标值，时间复杂度为O(log n) + O(n)
           :type nums: List[int]
           :type target: int
           :rtype: int
           """
   		index = self.binarySearch(nums, 0, len(nums), target)
   		if index != -1:
   			return index
   		else:
   			return self.findBigger(nums, target)
   	
   	def binarySearch(self, arr, low, high, key):
   		if low <= high:
   			mid = (low + high) // 2
   			if arr[mid] == key:
   				return mid
   			elif arr[mid] > key:
   				return self.binarySearch(arr, low, mid - 1, key)
   			elif arr[mid] < key:
   				return self.binarySearch(arr, mid + 1, high, key)
   		return -1
   	
   	def findBigger(self, arr, num):
   		if num < arr[0]:
   			return 0
   		if num > arr[len(arr) - 1]:
   			return len(arr)
   		for i in range(len(arr)):
   			if arr[i] < num:
   				continue
   			else:
   				break
   		return i
   	
   	def searchInsert1(self, nums, target):
   		"""
   		找到大于等于目标值的位置，该位置即为插入位置/目标值的位置。
           :type nums: List[int]
           :type target: int
           :rtype: int
           """
   		if target < nums[0]:
   			return 0
   		if target > nums[len(nums) - 1]:
   			return len(nums)
   		
   		for i in range(len(nums)):
   			if nums[i] >= target:
   				return i
   			elif nums[i] < target:
   				continue
   		return i
   	
   	def searchInsert2(self, nums, target):
   		"""searchInsert1的简化版"""
   		if target > nums[len(nums) - 1]:
   			return len(nums)
   		
   		for i in range(len(nums)):
   			if nums[i] < target:
   				continue
   			else:
   				break
   		return i
   	
   	def searchInsert3(self, nums, target):
   		"""
           二分查找变形
           不断用二分法逼近查找第一个大于等于 target的下标 
           """
   		l = 0
   		r = len(nums) - 1
   		while l <= r:
   			mid = l + (r - l) // 2
   			if nums[mid] < target:
   				l = mid + 1
   			else:
   				r = mid - 1
   		return l
   
   
   if __name__ == "__main__":
   	slt = Solution()
   	# result = slt.searchInsert([1, 3, 5, 6], 7)
   	# result = slt.searchInsert1([1, 3, 5, 6], 7)
   	# result = slt.searchInsert2([1, 3, 5, 6], 7)
   	result = slt.searchInsert3([1, 3, 5, 6], 7)
   	print(result)