博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
二分查找原理和实现
阅读量：5111 次
发布时间：2019-06-13

本文共 10620 字，大约阅读时间需要 35 分钟。

前言

的确，我一开始的时候也认为二分查找挺简单的，但是在我对二分查找进行总结的时候，发现虽然思路很简单，但是代码要写的正确就不容易了。

区间

需要注意的是

注意计算的区间是左闭右开区间[)还是左闭右闭区间[]，两者的代码是不太一样的。

左闭右闭区间

如果说你使用的是左闭右闭区间：

int search3(int array[], int n, int target) {
        int left = 0;    int right = n - 1; //比如说只有一个情况下    while (left <= right ) {
     //需要等于号，不然会进不来        int middle = left + (right - left) >> 1;        if (target < array[middle]) {
                right = middle - 1;        }        else if (target > array[middle]) {
                left = middle + 1;        }        else {
                return middle;        }    }    return -1;}

左闭右开区间

如果使用的是左闭右开区间：

// 左闭右开区间int search4(int array[], int n, int target) {
        int left = 0;    int right = n;    while (left < right) {
            int middle = left + (right - left) >> 1;        if (target < array[middle]) {
                right = middle;        }        else if (target > array[middle]) {
                left = middle + 1;        }        else {
                return middle;        }    }    return -1;}

lower_bound 和 upper_bound 和 binary_search 和 equal_range

我们可以发现，它们的代码是有区别的

左闭右闭区间，right = n - 1，left <= right，right = middle - 1

左闭右开区间，right = n，left < right，right = middle

为什么会这样呢？比如说n为1的时候，right此时为0，此时left也为0，需要等号才能进行while 循环。

还有需要注意的是，计算middle的时候，先计算减法是为了避免溢出。

STL的使用：

lower_bound：找到第一个 >= target的位置upper_bound：找到第一个 > target的位置

比如说给定的数组[1,2,2,2,3]

使用lower_bound返回的是第一个值为2的迭代器；使用upper_bound返回的是最后一个值为2的下一个，也就是值为3的迭代器；

使用lower_bound

  • 如果mid < val，显然mid本身及其左边的元素都不可能是答案了，则把first置为 mid + 1。
  • 如果mid >= val，答案可能是mid本身或者mid左边的元素，则把last置为mid。

使用upper_bound

  • 如果mid <= val，显然mid其左边的元素都不可能是答案了，则把first置为 mid + 1。
  • 如果mid > val，答案可能是mid右边的元素，所以把last设置成mid。

binary_search：查找某个元素是否出现

equal_range：查找某个元素出现的起止位置（终止位置为最后一次出现的位置加1）

实现

二分查找元素key的下标，如无return -1

有两个版本：

// 二分查找找数组下标int search(int array[], int low, int high, int target) {
        if (low > high) {
            return -1;    }    int mid = (low + high) / 2;    if (array[mid] < target) {
            return search(array, low, mid, target);    }    else if (array[mid] > target) {
            return search(array, mid + 1, high, target);    }    else {
            return mid;    }}// 迭代版本int search2(int array[], int low, int high, int target) {
        while (low <= high) {
            int mid = (low + high) / 2;        if (array[mid] > target) {
                high = mid-1;        }        else if (array[mid] < target) {
                low = mid+1;        }        else {
                return mid;        }    }    return -1;}

二分查找返回key（可能有重复）第一次出现的下标，如无return -1

// 求最小的i，使得a[i] = key，其实就是求有重复数值的数组中第一次出现key的下标// 重点在于不能要等于，如果(l <= r)这样的话，会导致陷入死循环，因为题目要求计算的是最小下标// 并且(a[m] < key)，所以导致r=m,l=r，会退出不了// 循环退出条件：left == rightint binary_search_1(int a[], int n, int key) {
        int m, l = 0, r = n - 1;//闭区间[0, n - 1]    while (l < r)    {
            m = l + ((r - l) >> 1);//向下取整        cout << ",m " << m;        if (a[m] < key) l = m + 1;        else r = m;    }    if (a[r] == key) return r;    return -1;}// 同上int binary_search_1_1(int a[], int n, int key) {
        int res = (int)(lower_bound(a, a + n, key) - a);    return (res == n || a[res] != key) ? -1 : res;}

二分查找返回key（可能有重复）最后一次出现的下标，如无return -1

// 求最大的i，使得a[i] = key，其实就是求有重复数值的数组中最后一次出现key的下标// 循环退出条件：left == right || left == right - 1int binary_search_2(int a[], int n, int key) {
        int m, l = 0, r = n - 1;//闭区间[0, n - 1]    while (l < r)    {
            m = l + ((r + 1 - l) >> 1);//向上取整        cout << ",m " << m;        if (a[m] <= key) l = m;        else r = m - 1;    }    if (a[l] == key) return l;    return -1;}// 同上int binary_search_2_2(int a[], int n, int key) {
        int res = (int)(upper_bound(a, a + n, key) - a);    return (res == 0 || a[res - 1] != key) ? -1 : res;}

二分查找返回刚好小于key的元素下标，如无return -1

// 求最大的i，使得a[i] < key，如果key已经是最小的了，则返回-1// 其实就是求一个key前一个位置的下标int binary_search_4(int a[], int n, int key) {
        int m, l = 0, r = n - 1;//闭区间[0, n - 1]    while (l < r)    {
            m = l + ((r + 1 - l) >> 1);//向上取整        cout << ",m " << m;        if (a[m] < key) l = m;        else r = m - 1;    }    if (a[l] < key) return l;    return -1;}// 同上int binary_search_4_4(int a[], int n, int key) {
        int res = (int)(lower_bound(a, a + n, key) - a);    return (res == 0) ? -1 : res;}

二分查找返回刚好大于key的元素下标，如无return -1

// 求最小的i，使得a[i] > key，如果key是最大的了，则返回-1// 其实就是求最后一个key的下一个位置的下标// 需要(a[m] <= key)，这样才能把相等的数值去除掉int binary_search_3(int a[], int n, int key){
        int m, l = 0, r = n - 1;//闭区间[0, n - 1]    while (l < r)    {
            m = l + ((r - l) >> 1);//向下取整        cout << ",m " << m;        if (a[m] <= key) l = m + 1;        else r = m;    }    if (a[r] > key) return r;    return -1;}// 同上int binary_search_3_3(int a[], int n, int key) {
        int res = (int)(upper_bound(a, a + n, key) - a);    return (res == n) ? -1 : res;}

全部的代码如下：

#include 
     
      using namespace std;// 二分查找找数组下标int search(int array[], int low, int high, int target) {
        if (low > high) {
            return -1;    }    int mid = (low + high) / 2;    if (array[mid] < target) {
            return search(array, low, mid, target);    }    else if (array[mid] > target) {
            return search(array, mid + 1, high, target);    }    else {
            return mid;    }}// 迭代版本int search2(int array[], int low, int high, int target) {
        while (low <= high) {
            int mid = (low + high) / 2;        if (array[mid] > target) {
                high = mid-1;        }        else if (array[mid] < target) {
                low = mid+1;        }        else {
                return mid;        }    }    return -1;}// 左闭右闭区间int search3(int array[], int n, int target) {
        int left = 0;    int right = n - 1; //比如说只有一个情况下    while (left <= right ) {
     //需要等于号，不然会进不来        int middle = left + (right - left) >> 1;        if (target < array[middle]) {
                right = middle - 1;        }        else if (target > array[middle]) {
                left = middle + 1;        }        else {
                return middle;        }    }    return -1;}// 左闭右开区间int search4(int array[], int n, int target) {
        int left = 0;    int right = n;    while (left < right) {
            int middle = left + (right - left) >> 1;        if (target < array[middle]) {
                right = middle;        }        else if (target > array[middle]) {
                left = middle + 1;        }        else {
                return middle;        }    }    return -1;}// 寻找包含某个值的区间［begin，end］void search5(int array[], int left, int right, int target, int& begin, int& end) {
        if (left >= right) {
            return ;    }    int mid = right - (right - begin)/2;    if (array[mid] == target) {
            if (mid < begin || begin == -1) {
                begin = mid;        }        if (mid > end) {
                end = mid;        }        search5(array, left, mid-1, target, begin, end);        search5(array, mid+1, right, target, begin, end);    }    else if (array[mid] > target) {
            search5(array, left, mid-1, target, begin, end);    }    else {
            search5(array, mid+1, right, target, begin, end);    }}// 求最小的i，使得a[i] = key，其实就是求有重复数值的数组中第一次出现key的下标// 重点在于不能要等于，如果(l <= r)这样的话，会导致陷入死循环，因为题目要求计算的是最小下标// 并且(a[m] < key)，所以导致r=m,l=r，会退出不了// 循环退出条件：left == rightint binary_search_1(int a[], int n, int key) {
        int m, l = 0, r = n - 1;//闭区间[0, n - 1]    while (l < r)    {
            m = l + ((r - l) >> 1);//向下取整        cout << ",m " << m;        if (a[m] < key) l = m + 1;        else r = m;    }    if (a[r] == key) return r;    return -1;}// 同上int binary_search_1_1(int a[], int n, int key) {
        int res = (int)(lower_bound(a, a + n, key) - a);    return (res == n || a[res] != key) ? -1 : res;}// 求最大的i，使得a[i] = key，其实就是求有重复数值的数组中最后一次出现key的下标// 循环退出条件：left == right || left == right - 1int binary_search_2(int a[], int n, int key) {
        int m, l = 0, r = n - 1;//闭区间[0, n - 1]    while (l < r)    {
            m = l + ((r + 1 - l) >> 1);//向上取整        cout << ",m " << m;        if (a[m] <= key) l = m;        else r = m - 1;    }    if (a[l] == key) return l;    return -1;}// 同上int binary_search_2_2(int a[], int n, int key) {
        int res = (int)(upper_bound(a, a + n, key) - a);    return (res == 0 || a[res - 1] != key) ? -1 : res;}// 求最小的i，使得a[i] > key，如果key是最大的了，则返回-1// 其实就是求最后一个key的下一个位置的下标// 需要(a[m] <= key)，这样才能把相等的数值去除掉int binary_search_3(int a[], int n, int key){
        int m, l = 0, r = n - 1;//闭区间[0, n - 1]    while (l < r)    {
            m = l + ((r - l) >> 1);//向下取整        cout << ",m " << m;        if (a[m] <= key) l = m + 1;        else r = m;    }    if (a[r] > key) return r;    return -1;}// 同上int binary_search_3_3(int a[], int n, int key) {
        int res = (int)(upper_bound(a, a + n, key) - a);    return (res == n) ? -1 : res;}// 求最大的i，使得a[i] < key，如果key已经是最小的了，则返回-1// 其实就是求一个key前一个位置的下标int binary_search_4(int a[], int n, int key) {
        int m, l = 0, r = n - 1;//闭区间[0, n - 1]    while (l < r)    {
            m = l + ((r + 1 - l) >> 1);//向上取整        cout << ",m " << m;        if (a[m] < key) l = m;        else r = m - 1;    }    if (a[l] < key) return l;    return -1;}// 同上int binary_search_4_4(int a[], int n, int key) {
        int res = (int)(lower_bound(a, a + n, key) - a);    return (res == 0) ? -1 : res;}int main() {
        int arr[4] = {
    3, 4, 5, 6};    int result1 = binary_search_1(arr, 4, 5);    cout << " result1:" << result1 << endl;    int result2 = binary_search_2(arr, 4, 5);    cout << " result2:" << result2 << endl;    int result3 = binary_search_3(arr, 4, 5);    cout << " result3:" << result3 << endl;    int result4 = binary_search_4(arr, 4, 5);    cout << " result4:" << result4 << endl;    return 0;}

下面是Python实现

import math# 第一个小于k的数def smallk(seq, k):    lo, hi = 0, len(seq)    while lo < hi:        mid = math.ceil((lo + hi) / 2) # 注意需要向上取整，而//是向下取整        if seq[mid] >= k:            hi = mid - 1        else:            lo = mid    return lo# 相同元素中第一个数def firstequalk(seq, k):    lo, hi = 0, len(seq)    while lo < hi:        mid = (lo + hi) // 2        if seq[mid] < k:            lo = mid + 1        else:            hi = mid    return lo# 第一个大于k的数def biggerk(seq, k):    lo, hi = 0, len(seq)    while lo < hi:        mid = (lo + hi) // 2        if seq[mid] <= k:            lo = mid + 1        else:            hi = mid    return lo# 相同元素中最后一个数def lastequalk(seq, k):    lo, hi = 0, len(seq)    while lo < hi:        mid = (lo + hi) // 2        if seq[mid] > k:            hi = mid - 1        else:            lo = mid    return lo

转载于:https://www.cnblogs.com/George1994/p/7532036.html

你可能感兴趣的文章
Html5 离线页面缓存
查看>>
《绿色·精简·性感·迷你版》易语言，小到不可想象
查看>>
Android打包key密码丢失找回
查看>>
VC6.0调试技巧（一）（转）
查看>>
类库与框架，强类型与弱类型的闲聊
查看>>
webView添加头视图
查看>>
php match_model的简单使用
查看>>
在NT中直接访问物理内存
查看>>
Intel HEX 文件格式
查看>>
SIP服务器性能测试工具SIPp使用指导(转)
查看>>
回调没用，加上iframe提交表单
查看>>
（安卓）一般安卓开始界面 Loding 跳转 实例 ---亲测！
查看>>
Mysql 索引优化 - 1
查看>>
LeetCode(3) || Median of Two Sorted Arrays
查看>>
大话文本检测经典模型：EAST
查看>>
待整理
查看>>
一次动态sql查询订单数据的设计
查看>>
C# 类(10) 抽象类.
查看>>
Vue_(组件通讯)子组件向父组件传值
查看>>
jvm参数
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-11-17 22:15:42   当前IP: 3.17.183.27   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我