• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

你真的会写二分查找吗

技术杂谈 勤劳的小蚂蚁 3周前 (04-01) 35次浏览 未收录 0个评论 扫描二维码

1、二分查找

二分查找是一个基础的算法,也是面试中常考的一个知识点。二分查找就是将查找的键和子数组的中间键作比较,如果被查找的键小于中间键,就在左子数组继续查找;如果大于中间键,就在右子数组中查找,否则中间键就是要找的元素。
/**
 * 二分查找,找到该值在数组中的下标,否则为-1
 */
static int binarySerach(int[] arrayint key) {
    int left = 0;
    int right = array.length – 1;
    // 这里必须是 <=
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] == key) {
            return mid;
        }
        else if (array[mid] < key) {
            left = mid + 1;
        }
        else {
            right = mid – 1;
        }
    }
    return -1;

}

每次移动leftright指针的时候,需要在mid的基础上+1或者-1, 防止出现死循环, 程序也就能够正确的运行。
注意:代码中的判断条件必须是while (left <= right),否则的话判断条件不完整,比如:array[3] = {1, 3, 5};待查找的键为5,此时在(low < high)条件下就会找不到,因为low和high相等时,指向元素5,但是此时条件不成立,没有进入while()中。

2、二分查找的变种

关于二分查找,如果条件稍微变换一下,比如:数组之中的数据可能可以重复,要求返回匹配的数据的最小(或最大)的下标;更近一步, 需要找出数组中第一个大于key的元素(也就是最小的大于key的元素的)下标,等等。 这些,虽然只有一点点的变化,实现的时候确实要更加的细心。
二分查找的变种和二分查找原理一样,主要就是变换判断条件(也就是边界条件),如果想直接看如何记忆这些变种的窍门,请直接翻到本文最后。下面来看几种二分查找变种的代码:

2.1、查找第一个与key相等的元素

查找第一个相等的元素,也就是说等于查找key值的元素有好多个,返回这些元素最左边的元素下标。
// 查找第一个相等的元素
static int findFirstEqual(int[] arrayint key) {
    int left = 0;
    int right = array.length – 1;
    // 这里必须是 <=
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] >= key) {
            right = mid – 1;
        }
        else {
            left = mid + 1;
        }
    }
    if (left < array.length && array[left] == key) {
        return left;
    }
    return -1;
}

2.2、查找最后一个与key相等的元素

查找最后一个相等的元素,也就是说等于查找key值的元素有好多个,返回这些元素最右边的元素下标。
// 查找最后一个相等的元素
static int findLastEqual(int[] arrayint key) {
    int left = 0;
    int right = array.length – 1;
    // 这里必须是 <=
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] <= key) {
            left = mid + 1;
        }
        else {
            right = mid – 1;
        }
    }
    if (right >= 0 && array[right] == key) {
        return right;
    }
    return -1;

}


2.3、查找最后一个等于或者小于key的元素

查找最后一个等于或者小于key的元素,也就是说等于查找key值的元素有好多个,返回这些元素最右边的元素下标;如果没有等于key值的元素,则返回小于key的最右边元素下标。
// 查找最后一个等于或者小于key的元素
static int findLastEqualSmaller(int[] arrayint key) {
    int left = 0;
    int right = array.length – 1;
    // 这里必须是 <=
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] > key) {
            right = mid – 1;
        }
        else {
            left = mid + 1;
        }
    }
    return right;
}

2.4、查找最后一个小于key的元素

查找最后一个小于key的元素,也就是说返回小于key的最右边元素下标。
// 查找最后一个小于key的元素
static int findLastSmaller(int[] arrayint key) {
    int left = 0;
    int right = array.length – 1;
    // 这里必须是 <=
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] >= key) {
            right = mid – 1;
        }
        else {
            left = mid + 1;
        }
    }
    return right;

}


2.5、查找第一个等于或者大于key的元素

查找第一个等于或者大于key的元素,也就是说等于查找key值的元素有好多个,返回这些元素最左边的元素下标;如果没有等于key值的元素,则返回大于key的最左边元素下标。
// 查找第一个等于或者大于key的元素
static int findFirstEqualLarger(int[] arrayint key) {
    int left = 0;
    int right = array.length – 1;
    // 这里必须是 <=
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] >= key) {
            right = mid – 1;
        }
        else {
            left = mid + 1;
        }
    }
    return left;
}

2.6、查找第一个大于key的元素

查找第一个等于key的元素,也就是说返回大于key的最左边元素下标。
// 查找第一个大于key的元素
static int findFirstLarger(int[] arrayint key) {
    int left = 0;
    int right = array.length – 1;
    // 这里必须是 <=
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] > key) {
            right = mid – 1;
        }
        else {
            left = mid + 1;
        }
    }
    return left;

}

3、二分查找变种总结

// 这里必须是 <=
while (left <= right) {
    int mid = (left + right) / 2;
    if (array[mid] ? key) {
        //… right = mid – 1;
    }
    else {
        // … left = mid + 1;
    }
}
return xxx;
二分查找变种较多,不过它们的“套路”是一样的,以上代码就是其套路,如何快速写出二分查找的代码,只需按照以下步骤即可:

1、首先判断出是返回left,还是返回right

因为我们知道最后跳出while (left <= right)循环条件是right < left,且right = left – 1。最后rightleft一定是卡在”边界值”的左右两边,如果是比较值为key,查找小于等于(或者是小于)key的元素,则边界值就是等于key的所有元素的最左边那个,其实应该返回left
以数组{1, 2, 3, 3, 4, 5}为例,如果需要查找第一个等于或者小于3的元素下标,我们比较的key值是3,则最后leftright需要满足以下条件:
我们比较的key值是3,所以此时我们需要返回left

2、判断出比较符号

int mid = (left + right) / 2;
if (array[mid] ? key) {
    //… right = xxx;
}
else {
    // … left = xxx;
}
也就是这里的if (array[mid] ? key) 中的判断符号,结合步骤1和给出的条件,如果是查找小于等于key的元素,则知道应该使用判断符号>=,因为是要返回left,所以如果array[mid]等于或者大于key,就应该使用>=,以下是完整代码
// 查找小于等于key的元素
int mid = (left + right) / 2;
if (array[mid] >= key) {
    right = mid – 1;
}
else {
    left = mid + 1;

}

参考:


丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:你真的会写二分查找吗
喜欢 (0)
[247507792@qq.com]
分享 (0)
勤劳的小蚂蚁
关于作者:
温馨提示:本文来源于网络,转载文章皆标明了出处,如果您发现侵权文章,请及时向站长反馈删除。

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00