有趣的二分

有趣的算法

对算法一直很陌生, 以后也会很陌生, 因为我是程序员,而不是数学家或者算法工程师
可这阻止不了算法的有趣.

先有了 快慢指针,让人眼前一亮, 而后这里的二分方法又让人 一个激动

二分的方法很简单, 上来就是去找你的 一半 去, 快速定位.

整理的复杂度也会跟 快速排序等方法有得一拼.

二分的关键, 是找到中间 的, 然后对中间的进行目标比较, 然后继续中间划分

这个获取中间的场景随着头尾的变动, 所以也是变动的. 我们要跟随着使用的场景去修改头尾

比较经典的场景就是去寻找一个数的插入位置. 这里有一个数字, 这里有一个数字, 我需要快速的找到这个数字应该插入的位置

//这个数组是假定已经排好顺序的, 这样这个二分才有意义
//定义好左右位置
//const target = 3.5
const arr = [1,2,3,4,5]

let l = arr.length;
let i = 0, // 最左侧的位置
    j = l - 1; //最右侧的位置
let mid = i + Math.floor((j-i)/2) // 或者可以使用位移 (j-i)>>1

let ret = l; //暂定我们要返回的就是最后一个点

//直接选择中间的位置进行比较,

arr[mid] > target
//如果中间的位置的数值比目标大, 那么数值肯定在中间以左, 我们需要修改右侧的位置(相对的mid也会变动)
j = mid - 1;

//如果相等, 那么正好, 我们要的目标就是这个地方
ret = mid;

//同理, 如果中间的位置小, 那么数字肯定在中间以右, 我们需要修改左侧的位置
i = mid + 1

//step2:
//因为正常情况下, 我们认为我们的元素是从小到大金星排列的, 所以正常的时候, 插入位置在右侧(>=)
//所以上边的判断可以合并

arr[mid] >= target
ret = mid
j = mid -1

//每次修改后, 我们需要重新计算 `mid`, 所以我们将方法进行整理后 ,如下

//左侧索引小于右侧, i = j, 也可以, 代表我们的遍历还是有元素的
while (i <= j) {
    let mid = i + Math.floor((j-i)/2);
    if (arr[mid] >= target) {
        ret = mid;
        j = mid - 1;
    }
    else {
        i = mid + 1
    }
}


//step3: 我们整理成完整的方法

function findPosition(arr, target) {
    let l = arr.length;
    let i = 0, // 最左侧的位置
    j = l - 1; //最右侧的位置
    let ret = l;
    while (i <= j) {
        let mid = i + Math.floor((j-i)/2);//可以使用位移的方法, >>
        let mid = i + (j-i>>1); //注意运算符优先级 位移操作的优先级是小于 + - 的
        if (arr[mid] >= target) {
            ret = mid;
            j = mid - 1;
        }
        else {
            i = mid + 1
        }
    }

    return ret;

}