二分查找&上下界查找【二分】对二分的初步理解
程序员文章站
2024-03-17 19:33:34
...
二分查找的复杂度为O(log N)
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
int BS(int a[],int size,int s) //非递归写法,s为需要查找的数
{
int l=0;
int r=size-1;
while(l <= r) {
int mid = l+(r-l)/2;
if(a[mid] == s)
return mid;
else if(a[mid] > s)
r = mid-1;
else
l = mid+1;
}
return -1;
}
int BSS(int a[],int l,int r,int s) //递归写法
{
if(l > r)
return -1;
int mid = l+(r-l)/2;
if(a[mid] == s)
return mid;
else if(a[mid] > s)
BSS(a,l,mid-1,s);
else
BSS(a,mid+1,r,s);
}
int LB(int a[],int size,int s)
{
int MAX = -1;
int l = 0;
int r = size-1;
while(l <= r) {
int mid = l+(r-l)/2;
if(a[mid] >= s)
r = mid-1;
else {
MAX = mid;
l = mid+1;
}
}
return MAX;
}
int UB(int a[],int size,int s)
{
int l = 0;
int r = size-1;
int MIN = inf;
while( l <= r) {
int mid = l+(r-l)/2;
if(a[mid] <= s)
l = mid+1;
else {
MIN = mid;
r = mid-1;
}
}
return MIN;
}
int main()
{
int a[10] = {8,5,6,9,2,10,5,2,4,6};
sort(a,a+10);
for(int i=0;i<10;i++)
cout << a[i] << " " ;
cout << endl;
cout << BS(a,10,2) <<endl; //二分查找非递归写法
cout << BSS(a,0,9,2) << endl; // 二分查找递归写法
cout << binary_search(a,a+10,2) << endl; // 库函数
cout << LB(a,10,5) << endl; // 最大下非递归
cout << lower_bound(a,a+10,5)-a << endl; // 返回[ ) 返回的是左边那个数小于s的 s地址 (嘴笨)
cout << UB(a,10,5) << endl;
cout << upper_bound(a,a+10,5)-a << endl; // 返回第一个大于s的数的地址
}
上一篇: 这是什么bug