leetcode 35 題

給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。
你可以假設(shè)數(shù)組中無(wú)重復(fù)元素。

示例 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) {
   // 比較第一個(gè)和最后一個(gè)
   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) 
       // 如果不符合條件則會(huì)變?yōu)?left > right 循環(huán)中止
   }
   // 循環(huán)中止后考慮情況
    return left;
};

模板 2：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
   // 比較第一個(gè)和最后一個(gè)
   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) 
       // 如果不符合條件則會(huì)變?yōu)?left === right 循環(huán)中止
   }
   // 循環(huán)中止后考慮情況
    return left;
};