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

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

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

想一想为什么图中时间复杂度为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

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

代码（非递归实现）：

#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。

版权所有：可定博客 © WNAG.COM.CN

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

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

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