二分问题:即[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,尊重他人劳动成果,谢过~
叨叨几句... 1 条评论