So i wrote a binary Search Program in C based of the Wikipedia Pseudocode but it keeps returning false even when dealing with Array of just one Element. I cant figure out where it goes wrong. Any help is appreciated! Btw, this is a coding challenge so i did not write the Test Suit myself.
EDIT: The Function is being tested as followed:
int arr[] = {6};
size_t length = sizeof(arr)/sizeof(*arr);
TEST_ASSER((&arr[0] == binary_search(6, arr, length));
int *binary_search(int value, const int *arr, size_t length) {
int L = 0;
int R = length - 1;
static int m;
while(L <= R) {
m = floor((L R) / 2);
if(arr[m] < value) {
L = m 1;
} else if(arr[m] > value) {
R = m - 1;
} else { return (&m); }
}
return 0;
}
EDIT: So it worked with the following Code after i removed the const term from the original function. Thanks for all your guys help!
int *binary_search(int value, int *arr, size_t length) {
int L = 0;
int R = length - 1;
static int m;
while(L <= R) {
m = (L R) / 2; // no floor needed
if(arr[m] < value) {
L = m 1;
} else if(arr[m] > value) {
R = m - 1;
} else {
return &arr[m];
}
}
return 0; // not found
}
CodePudding user response：
The length of the array is declared as having the type size_t
int *binary_search(int value, const int *arr, size_t length) {
So within the function the variables L, R and m also should be declared as having the type size_t.
Also using the function floor
m = floor((L R) / 2);
absolutely does not make a sense because the expression (L R) / 2 has the integer type int.
Declaring the variable m as static also does not make a great sense.
The function should return the position of the found element in the array or the size of the array if such an element is not found.
In this condition
TEST_ASSER((&arr[0] == binary_search(6, arr, length));
there are compared address of the first element of the array arr with the address of the static local variable m. It is evident that these objects occupy different extents of memory. So the condition will always evaluate to logical false.
The function can be declared an defined for example the following way as shown in the demonstrative program below.
#include <stdio.h>
size_t binary_search( const int a[], size_t n, int value )
{
size_t low = 0, high = n;
while ( low < high )
{
size_t middle = low ( high - low ) / 2;
if ( value < a[middle] )
{
high = middle;
}
else if ( a[middle] < value )
{
low = middle 1;
}
else
{
return middle;
}
}
return n;
}
int main(void)
{
int a[] = { 6 };
const size_t N = sizeof( a ) / sizeof( *a );
int value = 6;
size_t pos = binary_search( a, N, value );
if ( pos != N )
{
printf( "The value %d is found at position %zu\n", value, pos );
}
else
{
printf( "The value %d is not found.\n", value );
}
value = 5;
pos = binary_search( a, N, value );
if ( pos != N )
{
printf( "The value %d is found at position %zu\n", value, pos );
}
else
{
printf( "The value %d is not found.\n", value );
}
value = 7;
pos = binary_search( a, N, value );
if ( pos != N )
{
printf( "The value %d is found at position %zu\n", value, pos );
}
else
{
printf( "The value %d is not found.\n", value );
}
return 0;
}
The program output is
The value 6 is found at position 0
The value 5 is not found.
The value 7 is not found
Another approach is to define the function such a way that it will return a pointer to the found element in the array or NULL if such an element is not found.
Here is one more demonstrative program.
#include <stdio.h>
int * binary_search( const int a[], size_t n, int value )
{
size_t low = 0, high = n;
while ( low < high )
{
size_t middle = low ( high - low ) / 2;
if ( value < a[middle] )
{
high = middle;
}
else if ( a[middle] < value )
{
low = middle 1;
}
else
{
return ( int * )( a middle );
}
}
return NULL;
}
int main(void)
{
int a[] = { 6 };
const size_t N = sizeof( a ) / sizeof( *a );
int value = 6;
int *pos = binary_search( a, N, value );
if ( pos != NULL )
{
printf( "The value %d is found at position %tu\n", value, pos - a );
}
else
{
printf( "The value %d is not found.\n", value );
}
value = 5;
pos = binary_search( a, N, value );
if ( pos != NULL )
{
printf( "The value %d is found at position %tu\n", value, pos - a );
}
else
{
printf( "The value %d is not found.\n", value );
}
value = 7;
pos = binary_search( a, N, value );
if ( pos != NULL )
{
printf( "The value %d is found at position %tu\n", value, pos - a );
}
else
{
printf( "The value %d is not found.\n", value );
}
return 0;
}
The program output is the same as shown above.
The value 6 is found at position 0
The value 5 is not found.
The value 7 is not found.
CodePudding user response：
the logic of binary search should be like this
int *binary_search(int value, const int *arr, size_t length) {
int L = 0;
int R = length - 1;
static int m;
while(L <= R) {
m = floor((L R) / 2);
if(arr[m]==value)
{
// element found
}
else if(arr[m] < value) {
L = m 1;
} else if(arr[m] > value) {
R = m - 1;
}
}
return 0;
}
if while loop executed and not entered inside if(arr[m]==value) means element not in the list
CodePudding user response：
Your return statement returns the address of a local variable: &m. This is definitely wrong, as this memory is no longer allocated after the function returns, and it certainly is not the address that is expected in the driver code you have.
The quick fix is return &arr[m], but like said in comments, it is strange to return the address of an array element.
Just return the index, and adapt the function return type accordingly, and the driver code:
#include <stdio.h>
int binary_search(int value, const int *arr, size_t length) {
int L = 0;
int R = length - 1;
static int m;
while(L <= R) {
m = (L R) / 2; // no floor needed
if(arr[m] < value) {
L = m 1;
} else if(arr[m] > value) {
R = m - 1;
} else {
return m;
}
}
return -1; // not found
}
int main(void) {
printf("Hello World\n");
int arr[] = {6, 9, 13, 25};
size_t length = sizeof(arr)/sizeof(*arr);
if (1 == binary_search(6, arr, length)) {
printf("ok!\n");
}
return 0;
}