sakura 技术分享 2022-06-29

基础算法：二分查找、异或运算

作为一名程序员，不管是前端、后端、运维、测试、数据库、算法等等岗位，都是需要学习算法的，不仅能提升编程能力，还能提升思维逻辑、分析问题的能力，是IT职场必不可少的加薪技能。

千里之行，始于足下，最好的学习时间是一年前，其次是现在。最近在网上学习左程云老师的算法基础，记录下我的学习结果。

二分查找

例子1：有序数组某元素最左位置

给你一个n代表有一个长度为n的有序数组，然后给你一个k，你需要判断这个k是否在数组里面，如果存在就返回这个数从左往右第一次出现位置的下标，如果不存在输出-1。

思路：数组有序，所以可以使用二分查找，期间如果找到k，则下标赋给临时变量index，直到切成唯一元素（l === r），比较后返回。最终index为输出值。

let index = -1; 
find(0, N - 1, key, list);
// 有序数组arr里，下标从 l 到 r 之间，二分查找最左的key。
// 递归法：
const find = (l, r, key, arr) => {
    if (l > r) return;
    if (l === r) {
        if (arr[l] === key)  index = l;
        return;
    }
    // 二分
    let middle = l + ((r - l) >> 1);
    if (arr[middle] > key) {
        find(l, middle - 1, key, arr)
    }
    if (arr[middle] === key) {
        index = middle; // 找到临时最左，继续向左找
        find(l, middle - 1, key, arr)
    }
    if (arr[middle] < key) {
        find(middle + 1, r, key, arr)
    }
}

// 迭代法：
const find = (l, r, key, arr) => {
    let middle = 0;
    while(l <= r) {
        middle = l + ((r-l) >> 1);
        if (arr[middle] === key) {
            index = middle;
            r = middle - 1;
        }
        if (arr[middle] > key)  r = middle - 1;
        if (arr[middle] < key)  l = miidle + 1;
    }
}

二分查找的时间复杂度为：O(logN)。空间复杂度为O(1)。

而普通的从左向右遍历查询代码更简单，但是时间复杂度为：O(N)，如下：

const findKey = (l, r, key, arr) => {
    let index = -1;
    for (let i = l; i < r; i++) {
        if (arr[i] === key) { // 从左到右第一个
            index = i;
            break;
        }
        if (arr[i] > key) { // 大于则直接退出
            break;
        }
    }
    return index;
}

总结：当一个数组有序时候，查找某个元素的位置，或者查找某个元素最左（最右）的位置等等都可以使用二分查找，其时间复杂度为O(logN)。

例子2：有序数组元素>=k的最左位置

你需要输入一个n，一个数k，然后输入一个长度为n个大小的数组arr，然后你需要在arr上找满足>=K的最左位置，并且输出这个位置，如果不存在这个位置就输出-1。

输入描述:

第一行输入一个n，k
第二行输入长度为n的数组arr

思路：与例子1类似，改变一下判断条件即可。

(function(){
    // 递归法
    const find = (l, r, k, arr)=>{
        if (l > r) return;
        if (l === r) {
            if (arr[l] >= k)  index = l;
            return;
        }
        // 二分
        let middle = l + ((r - l) >> 1);
        if (arr[middle] >= k) {
            index = middle; // 找到临时最左，继续向左找
            find(l, middle - 1, k, arr)
        }
        if (arr[middle] < k) {
            find(middle + 1, r, k, arr)
        }
    }
    
    let a = readline().trim(),b = readline().trim();
     // 编码
    let N = Number(a.split(' ')[0]), k = Number(a.split(' ')[1]),
        list = b.split(' ').map((item) => Number(item));
    let index = -1;    
    find(0, N-1, k, list);
    print(index)

})();

// 迭代法：
const find = (l, r, key, arr) => {
    let middle = 0;
    while(l <= r) {
        middle = l + ((r-l) >> 1);
        if (arr[middle] >= key) {
            index = middle;
            r = middle - 1;
        }else{
            l = miidle + 1;
        }
    }
}

时间复杂度仍然为 O(logN)。

例子3：获取任意一个局部最小元素位置

定义局部最小的概念。arr长度为1时，arr[0]是局部最小。arr的长度为N(N>1)时，如果arr[0] < arr[1]，那么arr[0]是局部最小；
如果arr[N-1]<arr[N-2],那么arr[N-1]是局部最小；如果0<i<N-1，既有arr[i] < arr[i-1]，又有arr[i] < arr[i + 1]，那么arr[i]
是局部最小。给定无序数组arr,已知arr中任意两个相邻的数都不相等，只需要返回arr中任意一个局部最小出现的位置即可，如果不存在这个位置就输出-1。

(function(){
    // 迭代法
    const find = (l, r, arr)=>{
        if(r < 0) return -1
        if(r === 0) return 0 
        if (arr[0]< arr[1]) return 0
        if (arr[r] < arr[r-1]) return r
        while(l <= r) {
            if(l === r) return l
            let mid = l + ((r-l) >> 1)
            if(arr[mid] < arr[mid-1]) {
                if(arr[mid] < arr[mid+1]){
                    return mid
                }else {
                  l = mid + 1
                } 
            }else {
                r = mid - 1
            }
        }
        return -1
    }
    
    let N = Number(readline().trim()),b = readline().trim();
     // 编码
    let list = b.split(' ').map((item) => Number(item));
   
    print( find(0, N-1, list))

})();

异或运算

异或运算性质：

一个数异或0，则结果为这个数： a^0 = a。
一个数异或它自己，则结果为0： a^a = 0。
满足交换律和结合律：a^b^c == (a^b)^c == (a^c)^b。

例子1：找出数组中奇数次出现的一个数

一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到这一个数？

// N为数组arr的长度
const find = (N, arr) => {
    if(N < 1) return -1
    let res = 0
    for(let i = 0; i < N; i++) {
        res ^= arr[i] 
    }
    return res
}

例子2：找出数组中奇数次出现的两个数

给定一个数字arr，其中只有两个数字出现了奇数次，其它数字都出现了偶数次，按照从小到大顺序输出这两个数。

思路：

既然有两个奇数次出现的数，通过所有数字相异或可得出结果为（a^b），而且这两个数（a，b）必然至少有一位（二进制）是不同的，假设这位是第二位，a里为1，b里为0。==则数组中所有第二位为1的数相异或，结果必然为a；同理为0的相异或结果必为b。==

关键就是两点：如何计算ab中第几位不同；如果获取数组中所有第某位（假设称为关键位）为1的数。

// N为数组arr的长度
const find = (N, arr) => {
    if(N < 2) return -1
    // 初始值，考虑到连续异或，所以设置为0
    let a = 0, b = 0, eor = 0
    for(let i = 0; i < N; i++) {
        // eor值为 a^b
        eor ^= arr[i] 
    }
    // 获取ab中最右边位（关键位）为1的值，比如：0010
    let point = eor & (~eor + 1)
       
    for(let i = 0; i < N; i++) {
        // 如果这个数与 point 相与不为0，则这个数在关键位上为1，全部相异或则结果为a。
        if(arr[i] & point !== 0) {
            a ^= arr[i]
        }
    }
    b = point ^ a
    return a < b ? (a + ' ' + b) : (b + ' ' + a)
}