C中的二进制搜索代码不能正常工作
C中的二进制搜索代码不能正常工作
提问于 2020-05-01 11:18:05
我无法修复逻辑错误，因为我不知道这段代码中有什么问题。每次输入时，它都显示“元素未找到”。如果有人能在这方面帮我，我会很感激的。同样在这段代码中，我假设我们将数组的大小作为奇数，如果我们决定以偶数作为大小，该怎么办？
#include<stdio.h>
int main(){
int size;
printf("Enter the number of elemets(odd number) : ");
scanf("%d",&size);
int arr[size];
printf("Enter the elements in ascending order : ");
for(int i=0;i<size;i++){
scanf("%d",&arr[i]);
}
int element;
int flag=0;
printf("Enter element to be found : ");
scanf("%d",&element);
int low=0;
int high=size-1;
while(low<high){
int mid=(low+high)/2;
if(element<arr[mid]){
high=mid-1;
}
else if(element>arr[mid]){
low=mid+1;
}
else if(element==arr[mid]){
printf("Element %d found at pos %d ",element,mid);
flag=1;
break;
}
}
if(flag==0){
printf("Element not found");
}
return 0;
}回答 3
Stack Overflow用户
回答已采纳
发布于 2020-05-01 11:40:04
编辑：引用@TomKarze的更好答案
我以前的回答是：
您忽略了high==low的边界情况
#include<stdio.h>
int main(){
int size;
printf("Enter the number of elements(odd number) : ");
scanf("%d",&size);
int arr[size];
printf("Enter the elements in ascending order : ");
for(int i=0;i<size;i++){
scanf("%d",&arr[i]);
}
int element;
int flag=0;
printf("Enter element to be found : ");
scanf("%d",&element);
int low=0;
int high=size-1;
while(low<high){
int mid=(low+high)/2;
if(element<arr[mid]){
high=mid-1;
}
else if(element>arr[mid]){
low=mid+1;
}
else if(element==arr[mid]){
printf("Element %d found at pos %d ",element,mid);
flag=1;
break;
}
}
if(low==high && arr[low]==element) //Added 1 extra condition check that you missed
{
printf("Element %d found at pos %d ",element,low);
flag=1;
}
if(flag==0){
printf("Element not found");
}
return 0;
}Stack Overflow用户
发布于 2020-05-01 11:49:18
问题在于您的while测试。你有：
while(low<high) {
...
}如果所需的值位于该位置，则当low == high时，这将失败。通过将测试更改为：
while(low <= high) {
...
}这就是修复它所需的一切。您不需要添加任何特殊情况来“修复它”。只需确保您的数组是按升序排列的，并且它应该工作。
Stack Overflow用户
发布于 2020-05-01 12:48:11
对于数组的元素数，首先使用size_t类型。int类型的对象可以很小，以容纳数组中的元素数。
循环的这个条件
int high=size-1;
while(low<high){
//...是不正确的。例如，让我们假设数组只有一个元素。在这种情况下，由于初始化，high将等于0，因此等于left。
int high=size-1;因此，循环不会迭代，您将得到输入的数字没有在数组中找到，尽管数组的第一个和单个元素实际上将等于这个数字。
你需要改变这种情况
while ( !( high < low ) )
//...within语句中的此if语句
else if(element==arr[mid]){是多余的。你可以直接写
else // if(element==arr[mid]){如果执行二进制搜索的代码放在单独的函数中会更好。
下面是一个演示程序，它展示了如何编写这样的函数。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int binary_search( const int a[], size_t n, int value )
{
size_t left = 0, right = n;
int found = 0;
while ( !found && left != right )
{
size_t middle = left + ( right - left ) / 2;
if ( value < a[middle] )
{
right = middle;
}
else if ( a[middle] < value )
{
left = middle + 1;
}
else
{
found = 1;
}
}
return found;
}
int cmp( const void *a, const void *b )
{
int left = *( const int * )a;
int right = *( const int * )b;
return ( right < left ) - ( left < right );
}
int main(void)
{
const size_t N = 15;
srand( ( unsigned int )time( NULL ) );
for ( size_t i = 0; i < N; i++ )
{
size_t n = rand() % N + 1;
int a[n];
for ( size_t j = 0; j < n; j++ ) a[j] = rand() % N;
qsort( a, n, sizeof( int ), cmp );
for ( size_t j = 0; j < n; j++ )
{
printf( "%d ", a[j] );
}
putchar( '\n' );
int value = rand() % N;
printf( "The value %d is %sfound in the array\n",
value, binary_search( a, n, value ) == 1 ? "" : "not " );
}
return 0;
}例如，它的输出可能如下所示
0 2 2 3 4 5 7 7 8 9 10 12 13 13
The value 5 is found in the array
4 8 12
The value 10 is not found in the array
1 2 6 8 8 8 9 9 9 12 12 13
The value 10 is not found in the array
2 3 5 5 7 7 7 9 10 14
The value 11 is not found in the array
0 1 1 5 6 10 11 13 13 13
The value 7 is not found in the array
0 3 3 3 4 8 8 10 11 12 14 14 14 14
The value 3 is found in the array
0 5 5 10 11 11 12 13 13 14 14
The value 12 is found in the array
3 4 5 7 10 13 14 14 14
The value 14 is found in the array
0 3 3 7
The value 2 is not found in the array
1 6 9
The value 10 is not found in the array
2 2 3 3 4 4 4 5 5 6 8 8 9 13 13
The value 11 is not found in the array
11 11 13
The value 11 is found in the array
0 0 0 1 2 5 5 5 7 7 8 9 12 12 14
The value 6 is not found in the array
8 8 13
The value 1 is not found in the array
2 2 4 4 5 9 9 10 12 12 13 13 14 14
The value 14 is found in the array页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/61541452
复制相关文章
相似问题
腾讯云开发者
