LeetCode-简单-35-搜索插入位置(Java)

气死了，原本今天做的是中等难度的第二十九题两数相除，但力扣这编译器太气人了，不溢出不越界，在那里一直循环，加条件中断也不管不顾，我编译器都正常输出，测试都测试不了，INT_MAX次运算输出他们又显示不全，气死了。就换了个简单的题目放松一下。

不得不说，在这些基础函数的使用上，java和c真的是无缝切换。

题目

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

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

示例 1:

输入: [1,3,5,6], 5
输出: 2
示例 2:

输入: [1,3,5,6], 2
输出: 1
示例 3:

输入: [1,3,5,6], 7
输出: 4
示例 4:

输入: [1,3,5,6], 0
输出: 0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-insert-position
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

用的二分法，因为给的数组是排序好的。
当然，没排序好我们也可以把他排序好再算。

先设立两个位置，searchLeftSite与searchRightSite(下面简称lSite与rSite)，表示本次查找区间的左边和右边界限，初始值为0和数组长度。

每次循环，将target与区间中间数比较：

如果相等，则找到了target，输出中间位置。

如果target更大，要分两钟情况：
区间长度=1，此时直接输出右边界即可，原因见下面补充说明1
区间长度>1，此时将左边界增加一半的区间长度。

如果target更小，要分两钟情况：
区间长度=1，直接输出左边界
区间长度>1，将右边界减少一半区间长度。

补充说明1：
实际比较时，代码取得区间中间数是nums[(lSite+rSite)/2]，如果target不在nums数组中，那么最终一定会出现这么一个结果：
nums[lSite] < target < nums[rSite]，此时rSite = lSite+1。
此时target比较的对象nums[lSite+rSite]，可以写作nums[ (lSite*2 +1)/2 ]，即nums[lSite]，
因此，target与nums[lSite+rSite]的比较，实际上是target与nums[lSite]的比较，
所以，如果target更大，则取rSite作为输出，反之则取lSite作为输出。

补充说明2：
根据题目的要求，有三种特殊情况要先判断，
一种是target<=nums[0]，一种是target==nums[nums.length-1]，一种是target>nums[nums.length-1]，
直接当成特殊情况处理就好了，因为根据题目要求的不同，三种情况（实际是四种，但本体中有两种情况操作相同）的处理方式都可能不同。

代码

class Solution {
    public int searchInsert(int[] nums, int target) {
        int searchRightSite = nums.length;
        int searchLeftSite = 0;
        int temp;

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

        while(true){
            temp = (searchRightSite+searchLeftSite)/2;
            if(target == nums[temp]) return temp;
            else if(target >  nums[temp]){
                if(searchLeftSite+1 == searchRightSite) return searchRightSite;
                searchLeftSite += (searchRightSite-searchLeftSite)/2;
            }
            else{
                if(searchLeftSite+1 == searchRightSite) return searchLeftSite;
                searchRightSite -= (searchRightSite-searchLeftSite)/2;
            }
        }
    }
}