二分查找细节问题

6-10 二分查找 (20分)

如果一个递增的有序数量没有重复的数，标准的二分写法是这样的：

Position BinarySearch( List L, ElementType X )
{
	int left=1, right=L->Last;
	while(left<=right){
		int mid=(left+right)/2;
		if(X>L->Data[mid]) 
			left=mid+1;
		else if(X<L->Data[mid])
			right=mid-1;
		else return mid;  
	}
	return NotFound;
}

在这个程序中，如果查找的x在序列中如果有重复的，返回的x的位置是随机的。
如果查找的x有重复的，则有下面两种写法：

1.返回第一个等于x的数的位置

#include<stdio.h>
int b[10]={0,1,2,2,2,3};
int BinarySearch(int r,int x){
	int l=1,m;
	while(l<=r){
		m=(l+r)/2;
		if(b[m]<x){
			l=m+1;
		}
		else if(b[m]>=x){//等于的时候m一直往左移 
			r=m-1;
		} 
	}
	return l;
}
int main()
{
	int temp=BinarySearch(5,2);
	printf("%d %d",temp,b[temp]);
	return 0;
}

输入结果2 2

2.返回第一个大于x的数的位置

#include<stdio.h>
int b[10]={0,1,2,2,2,3};
int BinarySearch(int r,int x){
	int l=1,m;
	while(l<=r){
		m=(l+r)/2;
		if(b[m]>x){
			r=m-1;
		}
		else if(b[m]<=x){//等于的时候往右移 
			l=m+1;
		} 
	}
	return l;
}
int main()
{
	int temp=BinarySearch(5,2);
	printf("%d %d",temp,b[temp]);
	return 0;
}

输入结果5 3