每日算法----搜索插入位置----2020106（补）

目录

1. 题目描述2. 示例3. 思路4. 遇上的问题5. 具体实现代码6. 学习收获,官方一如既往的妙啊7 题目来源

1. 题目描述

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

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

2. 示例

3. 思路

一开始想要直接循环遍历直接报位置插入就好了，觉得太暴力了，就想用二叉树来遍历。

4. 遇上的问题

二叉树遍历过程中，前后端下标变动是前后端下标相加的和再除以2在循环过程中，判断跳出循环的条件太复杂了，也可能是我没有找到一个统一的跳出循环条件，最后是遇到问题解决问题。代码量太长了，这次的思路不行要多加学习！变量名没有因地制宜，可读性太差，一开始是为了避免使用过多变量导致内存损耗过多，现在结果看内存使用并没有得到改善

5. 具体实现代码

自己写的代码

class Solution { public int searchInsert(int[] nums, int target) { //得到数组最大下标 int n = nums.length-1; //得到数组最小下标 int i =0; //遍历，二分查找应该插入的位置， while(i<n){ //判断是否末端是否相等 if(nums[n]==target){ return n; } //判断前端是否相等 if(nums[i]==target){ return i; } // 当数组i和n差距1的时候会陷入死循环，死循环条件 if(i+1==n){ //当target不存在时 if(nums[i]<target&&nums[n]>target) return i+1; //当前端值大于target时 if(nums[i]>=target) return i; //当末端值小于target时 if(nums[n]<target) return n+1; //当末端值等于target时 if(nums[n]==target) return n; } //当中间值大于target，将末端下标跳转到中间值下标 if(nums[(n+i)/2]>target){ n = (n+i)/2; } //当中间值小于target，将前端下标跳转到中间值下标 else if(nums[(n+i)/2]<=target){ i = (n+i)/2; } } //当输入数组过小，存在i==n时，进行比较判断 if(i==n){ if(nums[i]>=target){ return i; } else{ return i+1; } } return i; } }

6. 学习收获,官方一如既往的妙啊

看了官方的二分查找，感觉自己算法的差劲程度。

public int searchInsert(int[] nums, int target) { //获得数组的长度 int n = nums.length; //获得前后端指针left、right，ans为传入的target插入下标 int left = 0, right = n - 1, ans = n; //当左指针大于右指针时跳出循环 while (left <= right) { //>>1是/2的意思，二进制运算更快！ int mid = ((right - left) >> 1) + left; //当target在left和mid中时 if (target <= nums[mid]) { //将mid赋给ans，ans作为边界值，之后如果target在left、right前后都可以避免情况。 ans = mid; //用中间值进行减1，从而避免了left和right永远差1的情况（我自己的算法犯的错误）。 right = mid - 1; } else { //当target在mid和right中时 //使用中间值+1，避免了左右指针永远差一的情况。 left = mid + 1; } } return ans; }

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/search-insert-position/solution/sou-suo-cha-ru-wei-zhi-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

妙是真的妙，毕竟我写的时候没有写得这么简单，我对二分查找的算法有了更进一步的了解，至少下次再用二分会比这次好太多了，注意的点是左右指针使用中间值下标进行加减，不要直接用相加再除以2赋值（造成永远差1的bug）。

7 题目来源

leetCode

---

快乐补题！------swrici