二分法原理

二分法查找也可以叫做折半查找；它是一种高效的查找方法。但是它要求线性表必须采用顺序存储结构，而且表中元素是有序排列。

以升序数列为例，比较一个元素与数列中的中间位置的元素的大小，如果比中间位置的元素大，则继续在后半部分的数列中进行二分查找；

如果比中间位置的元素小，则在数列的前半部分进行比较；如果相等，则找到了元素的位置。

每次比较的数列长度都会是之前数列的一半，直到找到相等元素的位置或者最终没有找到要找的元素。

在二分查找中，目标元素的查找区间的定义十分重要，只找对了区间，才能够减少计算找到正确的值

简单来说二分查找有以下几个步骤：

• 首先选择数组中间的数字和需要查找的目标值比较；如果相等最好，就可以直接返回答案了
• 如果不相等

• 如果中间的数字大于目标值，则中间数字向右的所有数字都大于目标值，全部排除
• 如果中间的数字小于目标值，则中间数字向左的所有数字都小于目标值，全部排除

时间复杂度

二分查找有个很重要的特点，就是不会查找数列的全部元素，而查找的数据量其实正好符合元素的对数，正常情况下每次查找的元素都在一半一半地减少。

所以二分查找的时间复杂度为

实战实验

看的再多的理论都是纸上谈兵，我们来实战一下

在有序数组[-1,0,3,4,6,10,13,14]找到13的下标

返回值：6

说明：13 出现在nums中并且下标为 6

具体的解题步骤可以拆分为以下几步：

• 第一步：初始化区间范围[left,right]
• 第二步：如果左区间值left小于等于右区间值right;开始进入循环

• 在循环体内找到中间点；判断中间点的值是不是目标值，如果是就返回
• 如果目标值 < nums[mid]，表示目标值可能在左半边，就重新赋值右区间
• 如果目标值 > nums[mid]，表示目标值可能在右半边，就重新赋值左区间

function search(nums, target) {
    // write code here
    // 在区间[left,right]中查找元素，左闭右闭
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        // 计算中间点
        let mid = parseInt(left + (right-left)/2);
        if (target == nums[mid]) {
            return mid;
         // 如果target < nums[mid]，表示目标值可能在左半边
        } else if (target < nums[mid]){
            right = mid - 1;
        // 如果target > nums[mid]，表示目标值可能在右半边
        } else if (target > nums[mid]){
            left = mid + 1;
        }
    }
    // 未找到返回-1
    return -1;
}
module.exports = {
  search: search,
};