欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分查找&上下界查找【二分】对二分的初步理解

程序员文章站 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的数的地址 
	 
}