35. Search Insert Position ( JavaScript )

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

解析：

这个常见解法就是二分法了，数组分两半，看要左边这半还是右边这半，再把这半边分两半，只是在判断要左半还是右半的时候，把下标值保存，如果是左边，保存左边下标值最大的那个，右边保存最小的那个，当最后发现右边保存的这个值要比左边这个值大了或者等于左边了，就可以返回了。

(The following English translation may not be right -.-)

analyze:

Solve this problem with dichotomy : divide the array into two halves from the middle, if the target should be in the left part, then remain the left part and store the 「index」largest one of the left part, if the target should be in the right part, we should store the 「index」smallest one of the right part, then continue divide the remaining half.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    if (!nums || !nums.length) return 0;
    
    var index = -1;
    var max = nums.length;
    var min = 0;
    while(index === -1) {
        // console.log('max, min: ', max, " ", min);
        var current = Math.floor((max + min) / 2);
        // console.log("current: ", current);
        if (nums[current] === target) {
            // console.log('index = ', current);
            index = current;
        } else if (nums[current] < target) {
            // console.log(nums[current]);
            min = current + 1;
        } else {
            // console.log('h', nums[current]);
            max = current;
        }
        if (max <= min) {
            // console.log('ind: ', min);
            index = min;
        }
    }
    return index;
};