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

作为一名程序员,不管是前端、后端、运维、测试、数据库、算法等等岗位,都是需要学习算法的,不仅能提升编程能力,还能提升思维逻辑、分析问题的能力,是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)
}

总结:

两个关键点已经给出,关键点1:获取ab中最右边位(关键位)为1的值 的方式比较特殊:一个数 与上 这个数按位非再加一的数,就是这个数中最右边位为1,其他位为0的数。目的是方便提取关键点2。

有问题反馈加微信:mue233 私聊送一本电子书,绝对受益良多! 微信公众号:慕意,分享创业、使用的软件和教程~
知识星球精选推荐 » 基础算法:二分查找、异或运算