Binary Search in C

[arnuld]

WANTED: To write a Binary Search algorithm (using C) to find a character
in string
WHAT I GOT: It works
PROBLEM: In some cases I can't comprehend the last comparison in output.
Check the last comparison (just after comparison with 'Z'):



#include <stdio.h>
#include <stdlib.h>
#include <string.h>


char binarySearch(const char, const char*, const size_t);

int main(int argc, char* argv[])
{
const char* arrc = "ABCDEFGHIJKLMNOPSTUVZ";
char c = '\0';
char f;

if(2 != argc)
{
fprintf(stderr,"USAGE: ./exec [character]\n");
exit(EXIT_FAILURE);
}
else
{
c = *(argv[1]);
}


printf("Finding '%c' inside '%s'\n\n", c, arrc);
f = binarySearch(c, arrc, strlen(arrc));
if(f)
{
printf("Element Found: %c\n", f);
}
else
{
printf("Nothing Found \n");
}

return 0;
}



char binarySearch(const char ele, const char* str, const size_t sz)
{
char retchar = '\0';
size_t begin = 0;
size_t end = sz;
size_t mid;

while(begin <= end)
{
char fnd;
mid = (begin + end) / 2;
fnd = *(str + mid);
/* printf("*str = %c, *(str + %u) = %c\n", *str, mid, *(str +
mid)); */
printf("fnd = %c, ele = %c\n", fnd, ele);
printf("begin = %u, end = %u, mid = %u\n", begin, end, mid);

if(ele > fnd)
{
printf("'%c' > '%c'\n", ele, fnd);
begin = mid + 1;
}
else if(ele < fnd)
{
printf("'%c' < '%c'\n", ele, fnd);
end = mid - 1;
}
else
{
printf("'%c' == '%c'\n", ele, fnd);
retchar = fnd;
break;
}
printf("-----------------------------------------\n\n");
}

return retchar;
}
===================== OUTPUT =======================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra binary-search.c
[arnuld@dune programs]$ ./a.out
USAGE: ./exec [character]
[arnuld@dune programs]$ ./a.out e
Finding 'e' inside 'ABCDEFGHIJKLMNOPSTUVZ'

fnd = K, ele = e
begin = 0, end = 21, mid = 10
'e' > 'K'
-----------------------------------------

fnd = S, ele = e
begin = 11, end = 21, mid = 16
'e' > 'S'
-----------------------------------------

fnd = V, ele = e
begin = 17, end = 21, mid = 19
'e' > 'V'
-----------------------------------------

fnd = Z, ele = e
begin = 20, end = 21, mid = 20
'e' > 'Z'

 

[Tobias Blass]

WANTED: To write a Binary Search algorithm (using C) to find a character
in string
WHAT I GOT: It works
PROBLEM: In some cases I can't comprehend the last comparison in output.
Check the last comparison (just after comparison with 'Z'):



#include <stdio.h>
#include <stdlib.h>
#include <string.h>


char binarySearch(const char, const char*, const size_t);

int main(int argc, char* argv[])
{
const char* arrc = "ABCDEFGHIJKLMNOPSTUVZ";
char c = '\0';
char f;

if(2 != argc)
{
fprintf(stderr,"USAGE: ./exec [character]\n");
exit(EXIT_FAILURE);
}
else
{
c = *(argv[1]);
}


printf("Finding '%c' inside '%s'\n\n", c, arrc);
f = binarySearch(c, arrc, strlen(arrc));
if(f)
{
printf("Element Found: %c\n", f);
}
else
{
printf("Nothing Found \n");
}

return 0;
}



char binarySearch(const char ele, const char* str, const size_t sz)
{
char retchar = '\0';
size_t begin = 0;
size_t end = sz;
size_t mid;

while(begin <= end)
{
char fnd;
mid = (begin + end) / 2;
fnd = *(str + mid);
/* printf("*str = %c, *(str + %u) = %c\n", *str, mid, *(str +
mid)); */
printf("fnd = %c, ele = %c\n", fnd, ele);
printf("begin = %u, end = %u, mid = %u\n", begin, end, mid);

if(ele > fnd)
{
printf("'%c' > '%c'\n", ele, fnd);
begin = mid + 1;
}
else if(ele < fnd)
{
printf("'%c' < '%c'\n", ele, fnd);
end = mid - 1;
}
else
{
printf("'%c' == '%c'\n", ele, fnd);
retchar = fnd;
break;
}
printf("-----------------------------------------\n\n");
}

return retchar;
}
===================== OUTPUT =======================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra binary-search.c
[arnuld@dune programs]$ ./a.out
USAGE: ./exec [character]
[arnuld@dune programs]$ ./a.out e
Finding 'e' inside 'ABCDEFGHIJKLMNOPSTUVZ'

fnd = K, ele = e
begin = 0, end = 21, mid = 10
'e' > 'K'
-----------------------------------------

fnd = S, ele = e
begin = 11, end = 21, mid = 16
'e' > 'S'
-----------------------------------------

fnd = V, ele = e
begin = 17, end = 21, mid = 19
'e' > 'V'
-----------------------------------------

fnd = Z, ele = e
begin = 20, end = 21, mid = 20
'e' > 'Z'
-----------------------------------------

fnd = , ele = e
begin = 21, end = 21, mid = 21
'e' > ''

In the last case (mid=21) you compare *(str+21) (== fnd) with your
element. Since strlen(str)==21, you get the terminating nullbyte.
perhaps you should adjust end to be sz-1.

 

[Ike Naar]

WANTED: To write a Binary Search algorithm (using C) to find a character
in string
WHAT I GOT: It works

Doubtful.
Did you try to run it for e.g. the characters '@', '?' or '3' ?

PROBLEM: In some cases I can't comprehend the last comparison in output.
Check the last comparison (just after comparison with 'Z'):

[big snip]

fnd = Z, ele = e
begin = 20, end = 21, mid = 20
'e' > 'Z'
-----------------------------------------

fnd = , ele = e
begin = 21, end = 21, mid = 21
'e' > ''

You mean the character on the right-hand-side of the ``>'' sign?
That's the null character at position 21 in the ``arrc'' array.

Not a surprise. The character that you're looking for ('e') does not
appear in ``arrc''.
Probably it's larger than the largest character in ``arrc''.

 

[Cristian-Matei Toader]

The program seems to work just fine. However in your example you are
comparing lowercase 'e' with uppercase letters, which seems
misleading. The lowercase letters have a higher ASCII value than the
uppercase ones, the binary search is always looking in the subsection
with higher values.

 

[Tobias Blass]

The program seems to work just fine. However in your example you are
comparing lowercase 'e' with uppercase letters, which seems
misleading. The lowercase letters have a higher ASCII value than the
uppercase ones, the binary search is always looking in the subsection
with higher values.

I think he wanted to do so. He searched for a nonexisting letter to
present the 'strange' empty char (the nullbyte at str+21)

 

[Barry Schwarz]

WANTED: To write a Binary Search algorithm (using C) to find a character
in string
WHAT I GOT: It works
PROBLEM: In some cases I can't comprehend the last comparison in output.
Check the last comparison (just after comparison with 'Z'):



#include <stdio.h>
#include <stdlib.h>
#include <string.h>


char binarySearch(const char, const char*, const size_t);

int main(int argc, char* argv[])
{
const char* arrc = "ABCDEFGHIJKLMNOPSTUVZ";
char c = '\0';
char f;

if(2 != argc)
{
fprintf(stderr,"USAGE: ./exec [character]\n");

Brackets are usually used to indicate optional parameters.

exit(EXIT_FAILURE);
}
else

When the if portion of a simple if-else construct ends with a
statement that jumps out of the normal sequence (e.g., return, break,
call to a function that does not return such as exit and abort), the
else is superfluous. Removing the else and the two braces would
result in the exact same execution sequence of statements.

{
c = *(argv[1]);
}


printf("Finding '%c' inside '%s'\n\n", c, arrc);
f = binarySearch(c, arrc, strlen(arrc));
if(f)
{
printf("Element Found: %c\n", f);
}
else
{
printf("Nothing Found \n");
}

return 0;
}



char binarySearch(const char ele, const char* str, const size_t sz)
{
char retchar = '\0';
size_t begin = 0;
size_t end = sz;
size_t mid;

while(begin <= end)
{
char fnd;
mid = (begin + end) / 2;
fnd = *(str + mid);
/* printf("*str = %c, *(str + %u) = %c\n", *str, mid, *(str +
mid)); */
printf("fnd = %c, ele = %c\n", fnd, ele);
printf("begin = %u, end = %u, mid = %u\n", begin, end, mid);

While size_t is definitely an unsigned integer, it need not be an
unsigned int. You should cast the expressions if you don't want to
use on the new C99 formats.

 

[arnuld]

if(2 != argc)
{
fprintf(stderr,"USAGE: ./exec [character]\n");

Brackets are usually used to indicate optional parameters.

Okay, understood.

When the if portion of a simple if-else construct ends with a statement
that jumps out of the normal sequence (e.g., return, break, call to a
function that does not return such as exit and abort), the else is
superfluous. Removing the else and the two braces would result in the
exact same execution sequence of statements.

Understood this as well.

While size_t is definitely an unsigned integer, it need not be an
unsigned int. You should cast the expressions if you don't want to use
on the new C99 formats.

casting a bigger type to smaller type, e.g. from long to int or even
unsigned int to int, may cause strange results if value can't fit in the
type being assigned too. Therefore I have to check for range errors,
something like:

if((ERANGE == errno && (INT_MAX == num || INT_MIN == num)) ||
(0 != errno && 0 == num))


Then 50% of the code will be there for error checking (mostly 60% of my
code is error-checking one). Is this the recommended way ?

 

[Barry Schwarz]

snip


casting a bigger type to smaller type, e.g. from long to int or even
unsigned int to int, may cause strange results if value can't fit in the
type being assigned too. Therefore I have to check for range errors,
something like:

if((ERANGE == errno && (INT_MAX == num || INT_MIN == num)) ||
(0 != errno && 0 == num))


Then 50% of the code will be there for error checking (mostly 60% of my
code is error-checking one). Is this the recommended way ?

Only if you want to play dumb.

What part of your code do you think will set errno? Why are you
testing unsigned values against INT_MIN?

All your values are less than 100 so casting them to an int would not
overflow. In any event, you were using %u so you should cast them to
unsigned int which cannot overflow (though it can produce unexpected
results).

If you really have to worry about an array in excess of 65536 bytes,
then cast the value to unsigned long and use %lu as your format. This
will support arrays up to 4GB. Just don't post your initialization
definition here when you have one that big.