C 中的二进制搜索（使用冒泡排序）
Binary Searching in C (with Bubble sort)
我写了一个二进制搜索的代码。它也提供了数组的冒泡排序。用户可以单独指定数组元素，也可以使用 RNG 生成数组元素。即使数组确实得到了正确排序，如果有匹配项我也无法获得正确的索引，即使匹配项不存在也无法以某种方式获得匹配项。编译代码时我没有收到任何错误或警告。请指教我的code/logic哪里错了。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
size_t binary_search(const int b[], int search, size_t low, size_t high);
int value = 0;
int main (void)
{
int selection=0,size=0,key=0; //Value will be used if the match doesn't exist in the array.
int temp=0,pass=0;
printf("\n\tThis program uses Binary Search Technique to find an element in an array.\n\n");
printf("\tThe user can either feed the individual array values or use the inbuilt Random Number Generator to initialise the array elements.\n");
printf("\tPress 1 for RNG fed array values.\n\tPress 2 for user fed array values.\n");
printf("\n\tSelection : ");
scanf("%d",&selection);
printf("\n\tPlease enter the size of the array : ");
scanf("%d",&size);
int a[size];
size_t i=0;
if (selection==1)
{
srand(time(NULL));
printf("\n\tThe random number generator will generate the values between 0 and 100");
for(i=0;i<size;i++)
a[i]=rand()%100;
}
else if (selection==2)
{
printf("\n\tPlease enter the array elements : \n");
for(i=0;i<size;i++)
{
printf("\tElement %d : ",i);
scanf("%d",&a[i]);
}
}
printf("\n\n\tThe array is : \n\n\t");
for(i=0;i<size;i++)
{
printf("%5d",a[i]);
if ((i+1)%20==0)
printf("\n\t");
}
for(pass=1;pass<i-1;pass++) //Bubble sort
{
for (i=0;i<size-1;i++)
{
if(a[i]>a[i+1])
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
}
}
}
printf("\n\n\tThe array after bubble sorting is : \n\n\t");
for(i=0;i<size;i++)
{
printf("%5d",a[i]);
if ((i+1)%20==0)
printf("\n\t");
}
printf("\n\n\tEnter the key value which is to be searched in the array : ");
scanf("%d",&key);
binary_search( a, key, 0, size-1);
if (value!=-1)
{
printf("\n\n\tKey found at a[%d].",value);
}
else
{
printf("\n\n\tNo match found.");
}
}
size_t binary_search(const int b[], int search, size_t low, size_t high)
{
int middle=0;
while (low<=high)
{
middle = (high+low)/2;
if (b[middle]==search)
return middle;
else if (search>b[middle])
{
low = middle+1;
}
else if (search<b[middle])
{
high = middle-1;
}
else
middle=-1;
}
return middle;
}
编辑：
我对代码进行了一些更改，如果找到匹配项，我可以从中获取索引。但是，当找不到匹配项时，我仍然无法获取消息。
匹配项不存在时的输出 1 :
请输入数组的大小：20
The random number generator will generate the values between 0 and 100
The array is :
80 76 14 56 78 60 70 43 55 4 87 25 18 54 36 20 48 73 21 55
The array after bubble sorting is :
4 14 18 20 21 25 36 43 48 54 55 55 56 60 70 73 76 78 80 87
Enter the key value which is to be searched in the array : 90
Key found at a[19].
进程返回 0 (0x0) 执行时间：4.759 秒
按任意键继续。
匹配项不存在时的输出2：
请输入数组的大小：20
The random number generator will generate the values between 0 and 100
The array is :
12 48 18 15 16 14 46 14 30 75 54 52 14 95 47 40 82 44 30 39
The array after bubble sorting is :
12 14 14 14 15 16 18 30 30 39 40 44 46 47 48 52 54 75 82 95
Enter the key value which is to be searched in the array : 5
对于这种情况，代码根本就没有结束。
全局变量 value 处理不正确。
您必须确保在有匹配项（即设置为匹配索引）和没有匹配项（即设置为表示不匹配的值）时将其设置在 binary_search 内.您当前的代码不会这样做。
显然你希望 value 在没有匹配项时为 -1，因此你需要：
size_t binary_search(const int b[], int search, int low, int high)
{
int middle=0;
while (low<=high)
{
middle = (high+low)/2;
if (b[middle]==search)
{
value = middle; // Match - save matching index
return middle;
}
else if (search>b[middle])
{
low = middle+1;
}
else if (search<b[middle]) // this if-part is not needed btw
{
high = middle-1;
}
}
value = -1; // No match
return 0;
}
也就是说，我强烈建议您停止为此使用全局变量。而是使用函数 return 值，如：
int binary_search(const int b[], int search, int low, int high)
{
int middle=0;
while (low<=high)
{
middle = (high+low)/2;
if (b[middle]==search)
{
return middle; // Match
}
else if (search>b[middle])
{
low = middle+1;
}
else if (search<b[middle]) // this if-part is not needed btw
{
high = middle-1;
}
}
return -1; // No match
}
（注意函数 return 现在是 int）
并像这样使用它：
int match = binary_search( a, key, 0, size-1);
if (match >= 0)
{
printf("\n\n\tKey found at a[%d].", match);
}
else
{
printf("\n\n\tNo match found.");
}
记得删除全局变量value
我将第 22 行从 int a[size]; 更改为
int *a = malloc(sizeof(int) * size);
和每个 scanf 到 scanf_s 因为我用 visual studio 到 运行 it
似乎排序工作正常，除非我们在数组中有零
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
size_t binary_search(const int b[], int search, size_t low, size_t high);
int value = 0;
int main(void)
{
int selection = 0, size = 1, key = 0; //Value will be used if the match doesn't exist in the array.
int temp = 0, pass = 0;
printf("\n\tThis program uses Binary Search Technique to find an element in an array.\n\n");
printf("\tThe user can either feed the individual array values or use the inbuilt Random Number Generator to initialise the array elements.\n");
printf("\tPress 1 for RNG fed array values.\n\tPress 2 for user fed array values.\n");
printf("\n\tSelection : ");
scanf_s("%d", &selection, sizeof(int));
printf("\n\tPlease enter the size of the array : ");
scanf_s("%d", &size, sizeof(int));
int *a = malloc(sizeof(int) * size);
size_t i = 0;
if (selection == 1)
{
srand(time(NULL));
printf("\n\tThe random number generator will generate the values between 0 and 100");
for (i = 0; i < size; i++)
a[i] = rand() % 100;
}
else if (selection == 2)
{
printf("\n\tPlease enter the array elements : \n");
for (i = 0; i < size; i++)
{
printf("\tElement %d : ", i);
scanf_s("%d", &a[i], sizeof(int));
}
}
printf("\n\n\tThe array is : \n\n\t");
for (i = 0; i < size; i++)
{
printf("%5d", a[i]);
if ((i + 1) % 20 == 0)
printf("\n\t");
}
for (pass = 1; pass < i - 1; pass++) //Bubble sort
{
for (i = 0; i < size - 1; i++)
{
if (a[i] > a[i + 1])
{
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
}
}
printf("\n\n\tThe array after bubble sorting is : \n\n\t");
for (i = 0; i < size; i++)
{
printf("%5d", a[i]);
if ((i + 1) % 20 == 0)
printf("\n\t");
}
printf("\n\n\tEnter the key value which is to be searched in the array : ");
scanf_s("%d", &key, sizeof(int));
binary_search(a, key, 0, size - 1);
if (value != -1)
{
printf("\n\n\tKey found at a[%d].", value);
}
else
{
printf("\n\n\tNo match found.");
}
}
size_t binary_search(const int b[], int search, size_t low, size_t high)
{
int middle = 0;
while (low <= high)
{
middle = (high + low) / 2;
if (b[middle] == search)
return middle;
else if (search > b[middle])
{
low = middle + 1;
}
else if (search < b[middle])
{
high = middle - 1;
}
}
value = middle;
return 0;
}
我写了一个二进制搜索的代码。它也提供了数组的冒泡排序。用户可以单独指定数组元素，也可以使用 RNG 生成数组元素。即使数组确实得到了正确排序，如果有匹配项我也无法获得正确的索引，即使匹配项不存在也无法以某种方式获得匹配项。编译代码时我没有收到任何错误或警告。请指教我的code/logic哪里错了。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
size_t binary_search(const int b[], int search, size_t low, size_t high);
int value = 0;
int main (void)
{
int selection=0,size=0,key=0; //Value will be used if the match doesn't exist in the array.
int temp=0,pass=0;
printf("\n\tThis program uses Binary Search Technique to find an element in an array.\n\n");
printf("\tThe user can either feed the individual array values or use the inbuilt Random Number Generator to initialise the array elements.\n");
printf("\tPress 1 for RNG fed array values.\n\tPress 2 for user fed array values.\n");
printf("\n\tSelection : ");
scanf("%d",&selection);
printf("\n\tPlease enter the size of the array : ");
scanf("%d",&size);
int a[size];
size_t i=0;
if (selection==1)
{
srand(time(NULL));
printf("\n\tThe random number generator will generate the values between 0 and 100");
for(i=0;i<size;i++)
a[i]=rand()%100;
}
else if (selection==2)
{
printf("\n\tPlease enter the array elements : \n");
for(i=0;i<size;i++)
{
printf("\tElement %d : ",i);
scanf("%d",&a[i]);
}
}
printf("\n\n\tThe array is : \n\n\t");
for(i=0;i<size;i++)
{
printf("%5d",a[i]);
if ((i+1)%20==0)
printf("\n\t");
}
for(pass=1;pass<i-1;pass++) //Bubble sort
{
for (i=0;i<size-1;i++)
{
if(a[i]>a[i+1])
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
}
}
}
printf("\n\n\tThe array after bubble sorting is : \n\n\t");
for(i=0;i<size;i++)
{
printf("%5d",a[i]);
if ((i+1)%20==0)
printf("\n\t");
}
printf("\n\n\tEnter the key value which is to be searched in the array : ");
scanf("%d",&key);
binary_search( a, key, 0, size-1);
if (value!=-1)
{
printf("\n\n\tKey found at a[%d].",value);
}
else
{
printf("\n\n\tNo match found.");
}
}
size_t binary_search(const int b[], int search, size_t low, size_t high)
{
int middle=0;
while (low<=high)
{
middle = (high+low)/2;
if (b[middle]==search)
return middle;
else if (search>b[middle])
{
low = middle+1;
}
else if (search<b[middle])
{
high = middle-1;
}
else
middle=-1;
}
return middle;
}
编辑： 我对代码进行了一些更改，如果找到匹配项，我可以从中获取索引。但是，当找不到匹配项时，我仍然无法获取消息。
匹配项不存在时的输出 1 : 请输入数组的大小：20
The random number generator will generate the values between 0 and 100
The array is :
80 76 14 56 78 60 70 43 55 4 87 25 18 54 36 20 48 73 21 55
The array after bubble sorting is :
4 14 18 20 21 25 36 43 48 54 55 55 56 60 70 73 76 78 80 87
Enter the key value which is to be searched in the array : 90
Key found at a[19].
进程返回 0 (0x0) 执行时间：4.759 秒 按任意键继续。
匹配项不存在时的输出2： 请输入数组的大小：20
The random number generator will generate the values between 0 and 100
The array is :
12 48 18 15 16 14 46 14 30 75 54 52 14 95 47 40 82 44 30 39
The array after bubble sorting is :
12 14 14 14 15 16 18 30 30 39 40 44 46 47 48 52 54 75 82 95
Enter the key value which is to be searched in the array : 5
对于这种情况，代码根本就没有结束。
全局变量 value 处理不正确。
您必须确保在有匹配项（即设置为匹配索引）和没有匹配项（即设置为表示不匹配的值）时将其设置在 binary_search 内.您当前的代码不会这样做。
显然你希望 value 在没有匹配项时为 -1，因此你需要：
size_t binary_search(const int b[], int search, int low, int high)
{
int middle=0;
while (low<=high)
{
middle = (high+low)/2;
if (b[middle]==search)
{
value = middle; // Match - save matching index
return middle;
}
else if (search>b[middle])
{
low = middle+1;
}
else if (search<b[middle]) // this if-part is not needed btw
{
high = middle-1;
}
}
value = -1; // No match
return 0;
}
也就是说，我强烈建议您停止为此使用全局变量。而是使用函数 return 值，如：
int binary_search(const int b[], int search, int low, int high)
{
int middle=0;
while (low<=high)
{
middle = (high+low)/2;
if (b[middle]==search)
{
return middle; // Match
}
else if (search>b[middle])
{
low = middle+1;
}
else if (search<b[middle]) // this if-part is not needed btw
{
high = middle-1;
}
}
return -1; // No match
}
（注意函数 return 现在是 int）
并像这样使用它：
int match = binary_search( a, key, 0, size-1);
if (match >= 0)
{
printf("\n\n\tKey found at a[%d].", match);
}
else
{
printf("\n\n\tNo match found.");
}
记得删除全局变量value
我将第 22 行从 int a[size]; 更改为
int *a = malloc(sizeof(int) * size);
和每个 scanf 到 scanf_s 因为我用 visual studio 到 运行 it
似乎排序工作正常，除非我们在数组中有零
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
size_t binary_search(const int b[], int search, size_t low, size_t high);
int value = 0;
int main(void)
{
int selection = 0, size = 1, key = 0; //Value will be used if the match doesn't exist in the array.
int temp = 0, pass = 0;
printf("\n\tThis program uses Binary Search Technique to find an element in an array.\n\n");
printf("\tThe user can either feed the individual array values or use the inbuilt Random Number Generator to initialise the array elements.\n");
printf("\tPress 1 for RNG fed array values.\n\tPress 2 for user fed array values.\n");
printf("\n\tSelection : ");
scanf_s("%d", &selection, sizeof(int));
printf("\n\tPlease enter the size of the array : ");
scanf_s("%d", &size, sizeof(int));
int *a = malloc(sizeof(int) * size);
size_t i = 0;
if (selection == 1)
{
srand(time(NULL));
printf("\n\tThe random number generator will generate the values between 0 and 100");
for (i = 0; i < size; i++)
a[i] = rand() % 100;
}
else if (selection == 2)
{
printf("\n\tPlease enter the array elements : \n");
for (i = 0; i < size; i++)
{
printf("\tElement %d : ", i);
scanf_s("%d", &a[i], sizeof(int));
}
}
printf("\n\n\tThe array is : \n\n\t");
for (i = 0; i < size; i++)
{
printf("%5d", a[i]);
if ((i + 1) % 20 == 0)
printf("\n\t");
}
for (pass = 1; pass < i - 1; pass++) //Bubble sort
{
for (i = 0; i < size - 1; i++)
{
if (a[i] > a[i + 1])
{
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
}
}
printf("\n\n\tThe array after bubble sorting is : \n\n\t");
for (i = 0; i < size; i++)
{
printf("%5d", a[i]);
if ((i + 1) % 20 == 0)
printf("\n\t");
}
printf("\n\n\tEnter the key value which is to be searched in the array : ");
scanf_s("%d", &key, sizeof(int));
binary_search(a, key, 0, size - 1);
if (value != -1)
{
printf("\n\n\tKey found at a[%d].", value);
}
else
{
printf("\n\n\tNo match found.");
}
}
size_t binary_search(const int b[], int search, size_t low, size_t high)
{
int middle = 0;
while (low <= high)
{
middle = (high + low) / 2;
if (b[middle] == search)
return middle;
else if (search > b[middle])
{
low = middle + 1;
}
else if (search < b[middle])
{
high = middle - 1;
}
}
value = middle;
return 0;
}