LeetCode算法之二分查找

前言

对于算法一直抱有恐惧感，觉得没有算法我也写了这么多代码，但周遭的环境让我感觉目前身为一名浅薄知识的敲代码的人，是需要去不断的汲取一些知识，所以就像大学学习英语单词一样，从Abandon开始，从查找开始。

二分查找

• 二分查找的前提：1.数组必须是有序的 2.数组中不存在重复元素
• 二分查找的边界：在写代码之前要清楚边界，才能确定循环条件到底是while(left <= right)，还是while(left <
  right)，到底是middle = right -1，还是 middle = right

所以会以两种情况来写

var search = function(nums, target) {
    let l = 0, r = nums.length - 1;//定义区间为[left, right]
    while(l <= r)//当 left = right时，区间[left, right]依然有效，所以使用 <=
    {
        let mid = parseInt(l + (r - l) / 2);//防止溢出，这里注意再js中 a/b是有小数位的，所以需要使用parseInt
        //let mid = l + (r -1) >> 2  在这里发现使用为运算反而会不保留小数位，更加方便
        if(nums[mid] === target) return mid;//找到目标值，返回mid
        l = nums[mid] < target ? mid + 1 : l;//当时nums[mid] < target成立，可以确定目标在右区间，因此缩小区间[mid + 1, right]
        r = nums[mid] < target ? r : mid - 1;//当时nums[mid] < target不成立，可以确定目标在左区间，因此缩小区间[left, mid - 1]        
    }
    return -1;
};

第二种情况

var search = function(nums, target) {
    let l = 0, r = nums.length - 1;
    while(l < r)
    {
        //let mid = parseInt(l + (r - l) / 2);
        let mid = l + ((r - l) >> 1);
        if(nums[mid] === target) 
            return mid;
        l = nums[mid] < target ? mid + 1 : l;
        r = nums[mid] < target ? r : mid;        
    }
    return -1;
};

这个算法写完，感觉对于基础的位运算需要再次复习一下，再往下又想到了计算机基础中，数据在内存中如何存储也需要复习一下