二分查找三种模板

leetcode 35 题

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

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

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

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

模板 1：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
   // 比较第一个和最后一个
   if(nums[0] > target) {
       return 0;
   }
   if(nums[nums.length - 1] < target) {
       return nums.length;
   }

   // 需要查找
   var left = 0;
   var right = nums.length;
   while(left < right) {
       var mid = Math.floor((left + right)/2);
       if(nums[mid] === target) {
           return mid;
       }
       if(nums[mid] > target) {
           // 向左查找
           right = mid - 1;
       } else {
           // 向右查找
           left = mid + 1;
       }
       // 最后一次查找情况：(left === right === mid) 
       // 如果不符合条件则会变为 left > right 循环中止
   }
   // 循环中止后考虑情况
    return left;
};

模板 2：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
   // 比较第一个和最后一个
   if(nums[0] > target) {
       return 0;
   }
   if(nums[nums.length - 1] < target) {
       return nums.length;
   }

   // 需要查找
   var left = 0;
   var right = nums.length;
   while(left < right) {
       var mid = Math.floor((left + right)/2);
       if(nums[mid] === target) {
           return mid;
       }
       if(nums[mid] > target) {
           // 向左查找
           right = mid;
       } else {
           // 向右查找
           left = mid + 1;
       }
       // 最终一次查找情况：(left < right 并相邻， mid === left) 
       // 如果不符合条件则会变为 left === right 循环中止
   }
   // 循环中止后考虑情况
    return left;
};