求助!c语言用二分法查找一个数出现的次数!
#include<stdio.h>
void main()
{
int arr[100];
int num,num1,temp;
int count=0;
printf("qign shu ru 100 ge shu zi !\n");
for(int i=0;i<100;i++)
{
scanf("%d",&num);
arr=num;
}
for(int x=0;x<99;x++)
{
for(int z=x+1;z<=99;z++)
{
if(arr[x]>arr[z])
{
temp=arr[x];
arr[x]=arr[z];
arr[z]=temp;
}
}
}
for(int j=0;j<100;j++)
{
printf("hehe%d\n",arr[j]);
}
printf("shu ru yao cha zhao de shu zi hehe!\n");
scanf("%d",&num1);
int mid;
int left=0,right=99;
mid=(left+right)/2;
while(left<=right)
{
if(arr[mid]==num1)
{
count++;
break;
}
else if(num1<arr[mid])
{
right=mid-1;
mid=(left+right)/2;
}
else
{
left=mid+1;
mid=(left+right)/2;
}
}
printf("shuzi %d chuxian %d ci\n",num1,count);
}
我觉得折半查找,找到那个数的话,程序就应该停止了。
怎么让他继续查找呢?用continue程序又停止不动了。
如果折半查找,那个数和mid的数字一样就在mid左右,例如 5,5,5
如果mid是等于中间的那个5,怎么在折半查找中让他识别它左右两个5??
求解啊! C printf
[解决办法]
可以分别用二分查找找出该数的左边界和右边界即可。。下边是一个简单的示例。。
#include <stdio.h>
int lower(int arr[], int key, int l, int r){
int ret = -1;
while(l <= r){
int mid = (l + r) / 2;
if(arr[mid] >= key){
ret = mid;
r = mid - 1;
}else l = mid + 1;
}
return ret;
}
int upper(int arr[], int key, int l, int r){
int ret = -1;
while(l <= r){
int mid = (l + r) / 2;
if(arr[mid] <= key){
ret = mid;
l = mid + 1;
}else r = mid - 1;
}
return ret;
}
int main(){
int arr[100] = { 0, 1, 2, 2, 2, 3};
int key = 2;
int lb = lower(arr, key, 0, 5);
if(lb >= 0 && arr[lb] == key){
int rb = upper(arr, key, 0, 5);
printf("%d\n", rb - lb + 1);
}
return 0;
}