LeetCode25 搜索插入位置

本文主要是介绍LeetCode25 搜索插入位置，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目

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

2. 示例

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

3. 解题思路
   1. 方法一：首先本题思路，找到第一个大于等于target的元素位置，即插入位置。所以直接遍历数组，找到第一个大于等于target的元素位置就是结果。但本题要求时间复杂度为log(n),那么需要进行优化。
   2. 方法二：二分查找。算法思路：将数组分成两份，left=0，mid=(left + right) / 2，right=length-1。根据mid与target的大小，进一步划分区域。如果mid>target，说明target在0到mid之间。反之，在mid到length-1之间。将范围缩小(left = mid + 1 或 right = mid - 1 ), 继续比较。本题可以用二分查找的思想，不过算法是查找相等数据，本题需要查找第一个大于等于的数据。
      1. 这里说明下为什么以left进行返回：
         本题结果即找到第一个大于等于target的元素。在二分查找的过程中，遇到的第一个mid对应元素，大于target时，mid对应的元素不一定是第一个大于target元素，只是二分查找过程中遇到的第一个。此时需要继续缩小范围就继续比较。
         那么什么情况下是第一个呢？首先mid对应元素和target相等的时候直接返回mid位置，即插入位置。大于的情况，因为数组中不存在target，那么一定会遍历到left==right==mid的时候，如果这个元素大于target，根据二分查找算法原理，此时right = mid - 1，left>right跳出循环，left即结果;如果这个元素小于target，left = mid+1，left>right跳出循环，left即结果(已经加1)。这里不管是大于还是小于，mid的其他位置都是已经确认了大于或小于target了。那么如果这个位置小于target，那么它后面的就是第一个大于target的，如果这个位置大于target那么他就是第一个大于target的。
4. 代码(Java)

   // 方法一
   class Solution {public int searchInsert(int[] nums, int target) {if (nums == null || nums.length == 0) {return -1;}if (nums[0] > target) {return 0;}if (nums[nums.length - 1] < target) {return nums.length;}for (int i = 0; i < nums.length; i++) {if (nums[i] >= target) {return i;}}return nums.length;}
   }

   // 方法二
   class Solution {public int searchInsert(int[] nums, int target) {if (nums == null || nums.length == 0) {return -1;}if (nums[0] > target) {return 0;}if (nums[nums.length - 1] < target) {return nums.length;}int left = 0;int right = nums.length - 1;while (left <= right) {int mid = (left + right) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return left;}
   }

这篇关于LeetCode25 搜索插入位置的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---