本文共 2958 字，大约阅读时间需要 9 分钟。

题目

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5Output: 2

Example 2:

Input: [1,3,5,6], 2Output: 1

Example 3:

Input: [1,3,5,6], 7Output: 4

Example 4:

Input: [1,3,5,6], 0Output: 0

我的尝试

分析一下：有序数组，给定一个数值，如果存在返回索引，不存在返回插入位置，假设没有重复元素

我的代码实现了，但是在leetcode上调试了很多次，发现忽略了很多情况：

1. 只有两个元素

2 小于第一个元素，大于最后一个元素。

3. 小于等于，不一样，如果小于当前元素，插入i-1，如果等于，插入i

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

优化解法

1.折半查询

1.1 递归形式

刚开始发现类似插入排序，但是不是排序，没有想起来用折半查找，看了leetcode的其他方法，恍然大悟，下面用折半查询实现一下：

public static  int binarySearch(int[] nums,int start,int end,int target) {       if (start>end){           return  -1;       }       int mid=(start+end)/2;       int key=nums[mid];       if (key==target){           return  mid;       }       if (key

写完后，发现运行不对，注意最后我写了return -1，逻辑对，但是返回结果始终都是-1，这个语句有问题。修改一下：

public static  int binarySearch(int[] nums,int start,int end,int target) {       if (start>end){           return  -1;       }       int mid=(start+end)/2;       int key=nums[mid];       if (key
   
    target){           binarySearch(nums,0,mid-1,target);       }       return mid;    }
   

虽然mid等于1，但是最后输出确实2，我debug发现退出递归时，外层mid一直发生变化，递归究竟发生了什么？？？经过debug，你会发现，其实mid计算出相等后，返回上层是，会执行return mid，这个时候mid值就会发生变化，所以出现错误。

其实我没有理解递归的本质，递归通过反复调用，关键是把深层次的结果层层返回。所以递归的调用语句前面必定会有return语句，否则递归运算的结果无法返回。我上面的代码就是，mid最终结果正确，但是没有返回。修改后如下：

public static  int binarySearch(int[] nums,int start,int end,int target) {       if (start>end){           return  -1;       }       int mid=(start+end)/2;       int key=nums[mid];       if(key==target){           return  mid;       }       if (key

针对本题目，如果找到返回就可以，如果没有找到，返回start索引就是要插入的位置，修改如下：

if (start>end){           //如果没有找到返回插入位置           return  start;       }       int mid=(start+end)/2;       int key=nums[mid];       if(key==target){           return  mid;       }       if (key

1.2 非递归形式

public static  int binarySearch(int[] nums,int start,int end,int target) {        int mid=0;        while(start<=end){            mid=(start+end)/2;            if (nums[mid]==target){                return  mid;            }            if (nums[mid]

2 两个指针迭代

看到有人提出两个指针迭代方法，类似于快速排序，其实就是一次快速排序，左边都比自己小，右边都比自己大，尝试一下：

public static  int quickSearch(int[] nums,int start,int end,int target) {       while (start<=end){           while (start<=end&&nums[start]
   
    target){               end--;           }           if (start
   

转载地址：https://kerry.blog.csdn.net/article/details/84063538 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！