二分查找与快速排序

二分查找

可以在在二分查找前进行排序，提高查找效率。
qsort() (快速排序，需要自定义比较函数)和bsearch()配合使用。

qsort() 函数的声明

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void , const void))

bsearch()函数声明

void* bsearch(const void*key,const void v,size_t size,int(comp)(const void,const void));

1. bsearch中的base必须是升序排列的数组！！！
2. 如果数组里有重复的答案，则bsearch会返回其中一个的地址 （具体返回哪一个不确定）
3. bsearch如果没找到所求则回传NULL ，否则回传该元素被找到的地址(void *)

两个函数的头文件都是#include <cstdlib>

#include <cstdlib>
#include <iostream>
#include <cstdlib>
using namespace std ;

//用于比较
int cmp(const void* _a, const void* _b)  
{
  int *a=(int *)_a;
  int *b=(int *)_b;
return *a-*b;
}

//展示数组元素
bool show_array(const int v[],const int &len)
{
	if (len<=0)
		return false;
	else
	{
	    cout<<"show the array:\n";
		for(int i = 0;i<len;++i)
			{
			    if (i==len-1) 
					cout<< v[i] <<endl;
				else 
					cout<< v[i] <<" ";
			
		    }
	}
}

int main(int argc, char** argv) {
	int v[10]={1,23,4,2,3,2,10,5,9,20};
    int target =3;
    qsort(v,10,sizeof(int),cmp);
    show_array(v,10);
    int* ptem=(int*)bsearch(&target, v,10,sizeof(int),cmp);
    if(ptem!=NULL)
    {
    	cout<<"find the target"<<endl;
		cout<<*ptem<<endl; //排序后在pos=3处
	}
	else{
		cout<<"don't find the target!\n";
	}
	return 0;
}

结果输出

show the array:
1 2 2 3 4 5 9 10 20 23
find the target
3