题目地址(35. 搜索插入位置)

https://leetcode-cn.com/problems/search-insert-position/

题目描述

  1. 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
  3. 请必须使用时间复杂度为 O(log n) 的算法。
  7. 示例 1:
  9. 输入: nums = [1,3,5,6], target = 5
  10. 输出: 2
  13. 示例 2:
  15. 输入: nums = [1,3,5,6], target = 2
  16. 输出: 1
  19. 示例 3:
  21. 输入: nums = [1,3,5,6], target = 7
  22. 输出: 4
  25. 示例 4:
  27. 输入: nums = [1,3,5,6], target = 0
  28. 输出: 0
  31. 示例 5:
  33. 输入: nums = [1], target = 0
  34. 输出: 0
  39. 提示:
  41. 1 <= nums.length <= 104
  42. -104 <= nums[i] <= 104
  43. nums 为无重复元素的升序排列数组
  44. -104 <= target <= 104

前置知识

  • 二分查找

公司

  • 暂无

思路

与二分查找一样 但是最后多加了个返回插入位置的条件

关键点

image.png
image.png
image.png
这时继续进入循环 触发了nums[mid] < target的条件 使得begin+1 也就是新元素插入的位置
image.png
如果情况改变 end比left小了 直接就返回left

所以无论是哪种情况 最后返回的应插入的元素的位置都是left

代码

  • 语言支持：Java

Java Code:

  2. class Solution {
  3.     public int searchInsert(int[] nums,
  4.                             int target) {
  5.         int begin = 0, end = nums.length - 1;
  6.         while (begin <= end) {
  7.             int mid = (begin + end) / 2;
  8.             if (nums[mid] > target) {
  9.                 end = mid - 1;
  10.             } else if (nums[mid] < target){
  11.                 begin = mid + 1;
  12.             }else {
  13.                 return mid;
  14.             }
  15.         }
  16.         return begin;
  17.     }
  18. }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：35. 搜索插入位置 - 图5#card=math&code=O%28logn%29&id=kvZyN)
  • 空间复杂度：35. 搜索插入位置 - 图6#card=math&code=O%28n%29&id=lsig7)