Thread: Binary Search Please check if it's right..

If you were attempting to implement a binary search algorithm, you missed the mark, BIG TIME.

Don't use "void main()", use "int main()".

> how about now?? it gives me an error when i use int main(), I'm using turbo c so may be it doesn't work in turbo c.
Well there's your problem

Turbo C is old... really old. Upgrade.

int main() should be fine in Turbo C - but compilers isn't like Whiskey - 10 year old Whiskey might be something to go looking for, 10 year old compilers are not so good...

Perhaps the error you get is "main doesn't return a value", in which case, the fix is to return 0 (unless you want your program to say "I didn't do what I was asked to do", in which case you should return a non-zero value).

Code:

		high=high;

Doesn't do much, does it?

I think you will want to check if you found the value before checking if high == low and exit - otherwise, you may not find the right value if it's exactly at the last point you search.

And there is an unused variable i in the bnsearch() function.

--
Mats

A couple tweaks for you.

Code:

#include<stdio.h>
#define SIZE 7
int bnsearch(int [],int,int,int);
int main()
{
	int arr[SIZE], i, element, pos, low = 0 , high = SIZE-1 ;
	printf("Enter &#37;d data values..\n", SIZE );
	for(i=0 ; i < SIZE ; i++ )
	{
		scanf("%d",&arr[i]);
	}
	printf("Enter Search element..\n");
	scanf("%d",&element);
	pos = bnsearch(arr,element,low,high);
	if(pos!=-1)
		printf("%d found at pos %d\n",element,pos);
	else
		printf("NUMBER NOT FOUND!\n");
	getchar();
	return 0 ; 
}
int bnsearch(int arr[],int element,int low,int high)
{
	int mid ;
	mid = (low+high) / 2 ;
	if(element==arr[mid]) return mid ;
	else if (high==low) return -1 ;
	else if(element>arr[mid]) return bnsearch(arr,element,mid+1,high) ;
	else return bnsearch(arr,element,low,mid-1) ;
}

Also, if your input values are not sorted ascending, the algorithm won't work.

Todd

Originally Posted by Adak

This is a binary search from --- <drum roll please>

Turbo C/C++ version 1.01

Enjoy!

That while loop version will be much more efficient than the recursive function call with 4 arguments.

Todd

As it sounds like this may have been handed in already, I'll point out the searching article on my website, which focuses mostly on binary search:
http://homepages.ihug.co.nz/~aurora7.../Searching.htm
One can go much further than even Adak's code, if writing an optimal search routine.

Bad news iMalc.

On paper, using your "most optimal search" routine, I worked through a simple search, and the algorithm didn't seem to work right. Then, I copied it into a c program, and sure enough, no worky.

Perhaps I've implemented it wrong?

Code:

#include<stdio.h>

#define NOT_FOUND -1 

int do_search(int a[], int find, int n) {
    int l = 0, r = n;
	
    while (l < r) {
        int m = (l + r) / 2;
        if (find < a[m])
            r = m;
        else
            l = m + 1;
    }
    if (a[l] == find)
        return l;
    else
        return NOT_FOUND;
}

int main() { 
	int a[] = {0,10,20,30,40,50,60,70}  ; 
	int rc = do_search(a, 50, 7) ; 
	printf("Item is &#37;d\n", rc) ; 
	return 0 ; 
}

Todd

Holy crap. How the hell did that happen!

I loaded up the copy of the source code in the project and that version was correct.
So I loaded up the web page in IE and that was wrong!
Then I loaded up my local copy of the site and it was wrong there too!
The if-else in the loop should read this:

Code:

		if (a[m] < find)
			l = m + 1;
		else
			r = m;

I've updated the page, and am investigating how that bug got in there, and double checking my unit tests right now, even though the souce code had it right already.
Thanks so much for finding that!

Note that the sample you posted is passing in the count as 7 when it should be 8, but that would only stop it from finding the last item.

Edit: Okay I've found where the bug came from. There is a very similiar if-else statement in the BinaryInsertionSort routine, except in that case it is supposed to be exactly matching the if-else in the code you posted above. The reason for that is that at some point I modified that sorting algorithm in order to make sure that the sort is stable. In BinaryInsertionSort the aim is to find the position of an item that is greater than the item being inserted. Whereas in the BinarySearch you want the opposite - the position of the item that is less than or equal to the value being searched for. My source code file was right all along, but aparently I misplaced the if-else statement from one into the other when copying the code into the html, as I updated them both at the same time - go figure!

OK, that fixes it! Thanks.

Also, the 7 is correct. The algorithm uses it as the last index, not as the number of elements.

Todd

Does it work?