leetcode35:搜索插入位置——学习笔记

题目：力扣https://leetcode-cn.com/problems/search-insert-position/

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

 思路：与leetcode34.在排序数组中查找元素的第一个和最后一个位置题目相似做法，同样是利用二分查找解题。这题相对与leetcode34还是稍微简单一些。大概思路仍然是，坚决不用线性查找，就是二分查找到底。利用中间位置mid的值与target比较，判断target可能在哪个区间内，然后再对哪个区间进行二分查找。若查找成功，找到target值，则直接返回其下标；若未找到target值，则需要再进行一次判断，观察target值是否大于查找的最终位置（若查找失败，mid的最后所处的位置就是需要插入的地方的附近），根据观察分别返回其对应的位置下标。

1.特殊情况处理。将那些数组长度为1或者2的情况先挑出来，处理掉它们。将它们可能出现的情况一一枚举解决掉。

if(nums.length==1){
    if(target<=nums[0]){
        return 0;
    }else{
        return 1;
    }
}else if(nums.length==2){
    if(target<=nums[0]){
        return 0;
    }else if(target>nums[1]){
        return 2;
    }else{
        return 1;
    }
}

2.设置变量left和right，分表代表左边界和右边界。这一次后续可能仍然需要用到mid，所以mid不放在后续循环内声明，而是提前声明好。

int left = 0;
int right = nums.length-1;
int mid = -1;

3.典型的二分查找。如果已经经历了leetcode34.在排序数组中查找元素的第一个和最后一个位置的洗礼，那么对这一块肯定是十分熟悉了。将nums[mid]与target作比较，根据比较结果确定target可能存在哪一个区间，然后再对该区间故技重施进行二分查找，直至找到target或者左边边界重合位置。

while(lefttarget){
        right = mid-1;
    }else if(nums[mid] 
4.选择性返回下标值。能执行这两行代码，意味着肯定是查找失败了（若查找成功，早就在上面的循环已经return，根本来不到这里。），因为上面的循环条件是left 
mid = (left+right)/2;
return nums[mid]>=target?mid:mid+1;
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5699724.html