leetcode题记：Search Insert Position

快来打我* 2022-05-21 13:40 122阅读 0赞

### 编程语言：java ###

### 提交结果： ###

62 / 62 test cases passed.
    Status: Accepted
    Runtime: 3 ms
    ps：运行时间和占用空间打败了100%的提交者，hhh

题目描述：  
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], 5
    Output: 2
    Example 2:
    
    Input: [1,3,5,6], 2
    Output: 1
    Example 3:
    
    Input: [1,3,5,6], 7
    Output: 4
    Example 4:
    
    Input: [1,3,5,6], 0
    Output: 0

### 解题思路： ###

二分查找的思路；一看到这道题，笔者看到已排序的数组，查找一个数字，首先想到的是经典的二分查找；但是，应用之前，应该先想清楚这个题目与二分查找的不同之处，在套用二分查找之前，应该先想清楚这道题目和二分查找的区别；
    与二分查找区别：查找的这个可能不存在与数组中；具体分为三种情况；
    第一，查找的数小于nums[0],比如[1,3,5,7]查找0
    第二，查找的数大于nums[nums.length-1],比如[1,3,5,7]查找9
    第三，查找的数介于nums两个数中间，比如[1,3,5,7]查找6
    针对这三种与二分查找的区别地方的思考：
    针对第一点，可以开始之前加入一个if语句，判断是否target小于nums[0],如果是，则返回0；
    针对第二点，加入if语句，判断是否target大于nums[nums.length-1].如果是，则返回nums.length.
    针对第三点，比如[1,3,5,7]查找6，循环结束时的条件(left>-right-1),即(循环执行条件为left<right-1)或者说已经明确找到某个值。所以当循环结束时，两种情况，找到这个值，或者没有找到。当没有找到的时候，能够确定这个值的位置一定在left索引与right索引之间。此时，left=rihgt-1，返回right索引即可。

### 难点： ###

找出与二分查找的区别之处并且给出相应的解决办法；

### 代码： ###

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