关于二分查找的那点事

发布于 2020-02-16  152 次阅读


二分问题:即[1,n]中拆成[1,x-1]和[x+1,n],若查找数>x,则在[x+1,n]中继续猜,尽可能逼近直至最后猜出来。

二分查找问题可看作如何在一个严格递增序列A中找出给定的数x。

下面给出在算法笔记中对于二分算法的算法流程。

17D470244695B141E66D1D652A45F2E0.png
268AAA20E8154F9B10F612B4AB011E92.png

想一想为什么图中时间复杂度为O(logn)?

假设总数据量是n,那二分查找无非就是用get(要查找的数)和n/2, n/4, n/8, ...... n/2^k进行比较,k是循环的次数
那么n/(2^k) <=1
那么我们令 n/(2^k) =1
k = log2(n)(是以2为底,n的对数)
那么T(n)是小于等于,并且接近于函数fn=(logn)
所以时间复杂度为O(logn)
二分查找的时间复杂度

下面给出在算法笔记中二分查找给出的示例。

给出11的查询过程,令left = 1,right = 10
6E2B4DE2727BF16F1330CCD3457C8485.png

给出34的查询过程,同样令left = 1,right = 10
A135F7296812BD0F3FE2579C890C19EB.png

代码(非递归实现):

#include<stdio.h>
//A[]必须是严格递增序列,如果不是,需要先用sort()函数
//其中left为二分下界,right为二分下界,x是想要查询的数
//二分区间是[left,right](左闭右闭),传入的初值是[0~n-1]
int binarySearch(int A[], int left, int right, int x){
    int mid;//left和right的中点,
    while(left < right){//只有left<right才能进行二分查找
        mid = (left + right)/2;
        if(A[mid] == x)return mid;
        if(a[mid] > x){//想要查找的数在mid的左边
            right = mid - 1;
        }else{//否则数在mid的右边
            left = mid + 1;
        }
    }
    return -1;//查找失败
}
int main(){
    const int = 10;
    int a[n] = {1, 4, 6, 7,  9, 10 , 23, 35, 38, 40};
    printf("%d %d\n", binarySearch(A, 0, n-1, 6),binarySearch(A, 0, n-1, 9));//第一个二分查找是在A序列里从0到n-1个元素查找数值为6的元素
    return 0;
}

一般题目中用的更多的是非递归的写法,递归的写法比较少。现给出递归写法:

#include <iostream>
#include<iomanip>
using namespace std;
int find(int A[], int left, int right, int k)
{
    int mid = (left + right) / 2;
    if (left <= right)
    {
        if (k > A[mid])
        {
            find(mid + 1, right, a, k);
        }
        else if (k < A[mid])
        {
            find(left, mid - 1, a, k);
        }
        else if (k == A[mid])
        {
            return mid;
        }
    }
    else return -1;
}
int main()
{
    int a[] = { 1,2,3,6,7,9,10 };
    cout<<find(a, 0, 6, 10);
    return 0;
}

注意:如果二分上界超过int型数据范围的一半,那么当想要查询的元素在序列叫靠后的位置时,语句mid = (left + right)/2 中的left+right就有可能超过int而导致溢出。
此时一般使用mid = left + (right - left)/2。

下面这篇文章会实现如何求出序列中第一个大于等于x的元素的位置,
以及第一个大于x的元素的位置R。

本文标题:《关于二分查找的那点事》

本文链接:https://wnag.com.cn/832.html

特别声明:除特别标注,本站文章均为原创,本站文章原则上禁止转载,如确实要转载,请电联:wangyeuuu@qq.com,尊重他人劳动成果,谢过~


正因为有要好好实现的梦想,所以今天也要好好加油。