二分查找

什么是二分查找

二分查找（Binary Search）

前提要求

1. 必须采用顺序存储结构
2. 必须为有序排列

   复杂度分析

• 时间复杂度 O(logN)

二分查找模板

模板一

二分法最基础形式，在数组中找出 target 的索引位置，如果不存在则返回 -1

 var search = function(nums, target) {
  let l = 0, r = nums.length - 1;
  while (l <= r) {
    const mid = l + Math.floor((r - l) >> 1);
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  return -1;
};

模板二

二分查找应用