定义

二分查找（二分搜索或折半搜索）是一种在有序数组中查找某一特定元素的搜索算法。

搜索过程从中间开始，如果中间元素正好是要查找的元素，则搜索过程结束；若果某一特定的元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，反复…

时间复杂度：O(logn)

例子：

leetcode 35.搜索插入位置

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

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

示例:

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

输出: 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

var searchInsert = function(nums, target) {
  var left = 0;
  var right = nums.length;
  while (left < right) {
    var mid = Math.floor((left + right) / 2);
    if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return left;
};