Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Binary Search in C

Reply
Thread Tools

Binary Search in C

 
 
arnuld
Guest
Posts: n/a
 
      12-27-2010
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' > ''
-----------------------------------------

Nothing Found
[arnuld@dune programs]$







--
http://www.lispmachine.wordpress.com
 
Reply With Quote
 
 
 
 
Tobias Blass
Guest
Posts: n/a
 
      12-27-2010


On Mon, 27 Dec 2010, arnuld wrote:

>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' > ''
>-----------------------------------------
>
>Nothing Found
>[arnuld@dune programs]$
>
>
>
>
>
>
>
>--
>http://www.lispmachine.wordpress.com
>

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.
 
Reply With Quote
 
 
 
 
Ike Naar
Guest
Posts: n/a
 
      12-27-2010
On 2010-12-27, arnuld <(E-Mail Removed)> wrote:
> 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.

> -----------------------------------------
> Nothing Found


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''.
 
Reply With Quote
 
Cristian-Matei Toader
Guest
Posts: n/a
 
      12-27-2010
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.

 
Reply With Quote
 
Tobias Blass
Guest
Posts: n/a
 
      12-27-2010


On Mon, 27 Dec 2010, Cristian-Matei Toader wrote:

>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)
 
Reply With Quote
 
Barry Schwarz
Guest
Posts: n/a
 
      12-27-2010
On 27 Dec 2010 12:07:49 GMT, arnuld <(E-Mail Removed)> wrote:

>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.

--
Remove del for email
 
Reply With Quote
 
arnuld
Guest
Posts: n/a
 
      12-28-2010
> On Mon, 27 Dec 2010 10:26:53 -0800, Barry Schwarz wrote:

>> On 27 Dec 2010 12:07:49 GMT, arnuld <(E-Mail Removed)> wrote:
>> if(2 != argc)
>> {
>> fprintf(stderr,"USAGE: ./exec [character]\n");


> Brackets are usually used to indicate optional parameters.


Okay, understood.



>> 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.


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 ?


--
http://www.lispmachine.wordpress.com
 
Reply With Quote
 
Barry Schwarz
Guest
Posts: n/a
 
      12-28-2010
On 28 Dec 2010 04:57:21 GMT, arnuld <(E-Mail Removed)> wrote:

>> On Mon, 27 Dec 2010 10:26:53 -0800, Barry Schwarz wrote:

>


snip

>> 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 ?


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.

--
Remove del for email
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Binary tree search vs Binary search Bogdan C Programming 22 10-21-2010 09:46 PM
binary search has a longer combinational delay than linear search sanborne VHDL 5 12-18-2009 10:27 PM
beginner with C : quick search or binary search help needed with forand while bpascal123@googlemail.com C Programming 9 07-03-2009 08:00 PM
Help understand probems - Binary Search and Sequenital Search Timmy C++ 5 07-09-2007 02:41 PM
Binary Search to search linearizer table? Andy C Programming 1 11-25-2003 04:40 AM



Advertisments