给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，返回其在数组中的位置，如果未找到返回-1。写出二分搜索的算法，并分析其时间复杂度。
template<class Type>
int BinarySearch(Type a[], const Type& x, int n)
{//在a[0:n]中搜索x，找到x时返回其在数组中的位置，否则返回-1
Int left=0; int right=n-1;
While (left<=right){
int middle=(left+right)/2;
if (x==a[middle]) return middle;
if (x>a[middle]) left=middle+1;
else right=middle-1;
}
Return -1;
}
时间复杂性为O(logn)
就写个二分法
#include <stdio.h>
#define N 15
int main()
{
int a[N]={12,13,15,19,20,23,25,30,31,32,35,39,41,42,43};//
int x;
int left=0,right=N;//left循环起点 right循环终点
int mid;
int i=0;
right=sizeof(a)/sizeof(a[0]);
printf("输入要查找的数：");
scanf("%d",&x);
while(left<=right)
{ mid=(left+right)/2;
if(x<a[mid])//如果X<中间数mid,则结束当前循环，开始下一轮循环从0~mid
{
right=mid-1;
}else if(x>a[mid])//如果X>中间数mid，则结束当前循环，开始下一轮循环从mid~N
{
left=mid+1;
}else{
mid++;
printf("%d是数组中第%d个元素\n",x,mid);
return 0;
}
}
printf("无此数\n");
return 0;
}
函数形式
#include <stdio.h>
#define N 15
int BinarySearch(int a[],int x)
{
int left=0,right=N;//left循环起点 right循环终点
int mid;
while(left<=right)
{ mid=(left+right)/2;
if(x<a[mid])//如果X<中间数mid,则结束当前循环，开始下一轮循环从0~mid
{
right=mid-1;
}else if(x>a[mid])//如果X>中间数mid，则结束当前循环，开始下一轮循环从mid~N
{
left=mid+1;
}else{
return mid;
}
}
return -1;
}
int main()
{
int a[N]={12,13,15,19,20,23,25,30,31,32,35,39,41,42,43};//
int x,index;
printf("输入要查找的数：");
scanf("%d",&x);
index=BinarySearch(a,x);
if(index>=0)
printf("在数组中的下标是%d",index);
else
printf("无此数");
return 0;
}
调用的话，直接传了对应参数，findNum(a,数组下标起始位置,数组下标结束位置,目标值)
int findNum(int a[], int left, int right, int target) {
if (left > right) {
return -1;
} else {
int mid = (left + right) / 2; //中间的下标
if (target == a[mid])
return mid;
else if (target < a[mid])
return findNum(a, left, mid - 1, target);
else
return findNum(a, mid + 1, right, target);
}
}
二分法，时间复杂度就是O(logN)