I have written a code for Binary Search. It has a provision for bubble sorting of array too. The user can either specify the array elements individually or use an RNG for generate the array elements. Even if the array does get sorted properly, I am unable to get the correct index if there is a match and somehow getting a match even if the match doesn't exist. I get no errors or warnings while compiling the code. Please advice on where my code/logic is wrong.
#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("]",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("]",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;
}
Edit : I have made some changes to the code from which I am able to get the index if a match is found. However, I am still unable to get the msg when a match isn't found.
Output for when match doesnt exist 1 : Please enter the size of the array : 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].
Process returned 0 (0x0) execution time : 4.759 s Press any key to continue.
Output when match doesnt exist 2: Please enter the size of the array : 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
For this case, the code doesnt end at all.
CodePudding user response：
The global variable value is not handled correct.
You must make sure to set it inside binary_search both when you have a match (i.e. set it to matching index) and when you have no match (i.e. set it to a value indicating no-match). Your current code doesn't do that.
Apparently you want value to be -1 when you don't have a match so you need:
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;
}
That said, I strongly recommend that you stop using a global variable for this. Instead use the functions return value like:
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
}
(notice that the function returns an int now)
and use it like:
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.");
}
Remember to delete the global variable value
CodePudding user response：
I changed line 22 from int a[size]; to
int *a = malloc(sizeof(int) * size);
and each of scanf to scanf_s because I used visual studio to run it
It seems that the sort works fine except when we have zeros in the array
#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("]", 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("]", 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;
}