leetcode-javascript-35. 搜索插入位置

https://leetcode-cn.com/problems/search-insert-position/
示例 1:

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

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

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

暴力查找

var searchInsert = function(nums, target) {
    for(let i = 0; i<nums.length; i++){
       if(target == nums[i]){
           return i
       }else if(target > nums[i] && target <nums[i+1]){
           return i+1
           
       }else{
           if(target > nums[nums.length-1]){
               return nums.length
           }else if(target < nums[0]){
               return 0
           }
           //return nums.indexOf(target)
       }
    }
};
//简化
var searchInsert = function(nums, target) {
    //jugde two part first
    if(target > nums[nums.length-1]){
               return nums.length
    }else if(target < nums[0]){
               return 0
    }
    //judge middle one
    for(let i = 0; i<nums.length; i++){
       if(target == nums[i]){
           return i
       }else if(target > nums[i] && target <nums[i+1]){
           return i+1
           
       }
    }
};

二分法

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let left = 0; let right = nums.length -1;
    while(left <= right) {
        let mid = Math.floor((left+right)/2)
        if(target == nums[mid]){
            return mid
        }else if(nums[mid]<target){//left move to right
            left = mid +1
            // console.log(left)
        }else {
            right = mid-1
        }
    }
    return left //left move to right
};

//java
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            System.out.printf("simple integer: %d", mid);
            if(nums[mid] == target) { 
                return mid;
            } else if(nums[mid] < target) {
                // 0 1 3 4
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }  
        return left;
    }
}

//python
from typing import List


class Solution:

    def searchInsert(self, nums: List[int], target: int) -> int:
        # 返回大于等于 target 的索引，有可能是最后一个
        size = len(nums)
        # 特判
        if size == 0:
            return 0

        left = 0
        # 如果 target 比 nums里所有的数都大，则最后一个数的索引 + 1 就是候选值，因此，右边界应该是数组的长度
        right = size
        # 二分的逻辑一定要写对，否则会出现死循环或者数组下标越界
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                assert nums[mid] >= target
                # [1,5,7] 2
                right = mid
        # 调试语句
        # print('left = {}, right = {}, mid = {}'.format(left, right, mid))
        return left

二分法模板 解决返回left 还是right
理由很简单：写 while (left < right) 的时候，退出循环时，左边界等于右边界，因此你不必纠结要返回 left 还是 right ，此时返回 left 或者 right 都是可以的。
2、如果你的业务逻辑不能保证你要找的数一定在左边界和右边界所表示的区间里出现，那么只要在退出循环以后，再针对 nums[left] 或者 nums[right] （此时 nums[left] == nums[right]）单独作一次判断，看它是不是你要找的数即可，这一步操作常常叫做“后处理”。

（1）当 left 和 right 是很大的整数的时候，如果写 int mid = (left + right) / 2; 这里 left + right 的值就有可能超过 int 类型能表示的最大值，因此使用 mid = left + (right - left) // 2 可以避免这种情况。

public class Solution {
//退出left = right 所以 返回left 和right 都一样
//
    public int searchInsert(int[] nums, int target) {
        int len = nums.length;

        if (len == 0) {
            return 0;
        }

        int left = 0;
        int right = len;

        while (left < right) {
            int mid = left + (right - left) / 2;//取左边 所right 不 -1
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}