Binary Search Please check if it's right..

This is a discussion on Binary Search Please check if it's right.. within the C Programming forums, part of the General Programming Boards category; Code: #include<stdio.h> #include<conio.h> int bnsearch(int [],int,int,int,int); void main() { int arr[10],i,element,pos,low,high,size=10; printf("Enter data..\n"); for(i=0;i<10;i++) { scanf("%d",&arr[i]); } printf("Enter Search element..\n"); ...

  1. #1
    Registered User
    Join Date
    Apr 2008
    Posts
    15

    Binary Search Please check if it's right..

    Code:
    #include<stdio.h>
    #include<conio.h>
    int bnsearch(int [],int,int,int,int);
    void main()
    {
    	int arr[10],i,element,pos,low,high,size=10;
    	printf("Enter data..\n");
    	for(i=0;i<10;i++)
    	{
    		scanf("%d",&arr[i]);
    	}
    	printf("Enter Search element..\n");
    	scanf("%d",&element);
    	low=0;
    	high=10;
    	pos=bnsearch(arr,element,size,low,high);
    	printf("Element found at pos %d\n",pos);
    	getch();
    }
    int bnsearch(int arr[],int element,int size,int low,int high)
    {
    	int mid,i,b=0;
    	mid=(low+high)/2;
    	printf("mid is : %d\n",mid);
    	for(i=low;i<=mid;i++)
    	{
    		if(arr[i]==element)
    			return i;
    	}
    	low=mid+1;
    	for(i=low;i<=high;i++)
    	{
    		if(arr[i]==element)
    			return i;
    	}
    	printf("low is : %d\n",low);
    	bnsearch(arr,element,size,low,high);
    }
    Please check if it's right, i think i'm getting right output, but not sure...

  2. #2
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    If you were attempting to implement a binary search algorithm, you missed the mark, BIG TIME.

    Don't use "void main()", use "int main()".
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  3. #3
    Registered User
    Join Date
    Apr 2008
    Posts
    15
    Code:
    #include<stdio.h>
    #include<conio.h>
    #define size 7
    int bnsearch(int [],int,int,int);
    void main()
    {
    	int arr[size],i,element,pos,low,high;
    	printf("Enter data..\n");
    	for(i=0;i<size;i++)
    	{
    		scanf("%d",&arr[i]);
    	}
    	printf("Enter Search element..\n");
    	scanf("%d",&element);
    	low=0;
    	high=size-1;
    	pos=bnsearch(arr,element,low,high);
    	if(pos!=-1)
    		printf("%d found at pos %d\n",element,pos);
    	else
    		printf("NUMBER NOT FOUND!\n");
    	getch();
    }
    int bnsearch(int arr[],int element,int low,int high)
    {
    	int mid,i;
    	mid=(low+high)/2;
    	if(high==low)
    	{
    		return -1;
    	}
    	if(element==arr[mid])
    		return mid;
    	else if(element>arr[mid])
    	{
    		low=mid+1;
    		high=high;
    		return bnsearch(arr,element,low,high);
    	}
    	else
    	{
    		high=mid-1;
    		return bnsearch(arr,element,low,high);
    	}
    }
    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.

  4. #4
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    > 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.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Registered User
    Join Date
    Apr 2008
    Posts
    15
    Code:
    #include<stdio.h>
    #include<conio.h>
    #define size 7
    int bnsearch(int [],int,int,int);
    void main()
    {
    	int arr[size],i,element,pos,low,high;
    	printf("Enter data..\n");
    	for(i=0;i<size;i++)
    	{
    		scanf("%d",&arr[i]);
    	}
    	printf("Enter Search element..\n");
    	scanf("%d",&element);
    	low=0;
    	high=size-1;
    	pos=bnsearch(arr,element,low,high);
    	if(pos!=-1)
    		printf("%d found at pos %d\n",element,pos);
    	else
    		printf("NUMBER NOT FOUND!\n");
    	getch();
    }
    int bnsearch(int arr[],int element,int low,int high)
    {
    	int mid,i;
    	mid=(low+high)/2;
    	if(high==low&&element!=arr[mid])
    	{
    		return -1;
    	}
    	if(element==arr[mid])
    		return mid;
    	else if(element>arr[mid])
    	{
    		low=mid+1;
    		high=high;
    		return bnsearch(arr,element,low,high);
    	}
    	else
    	{
    		high=mid-1;
    		return bnsearch(arr,element,low,high);
    	}
    }
    Well it works, thanks everyone for taking time to look at the code and giving advice, i really appreciate it.

    hey hey it's old, but it's gold like OLD IS GOLD

    Have a nice day.

  7. #7
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    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
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    This is a binary search from --- <drum roll please>

    Turbo C/C++ version 1.01

    Enjoy!

    It's searching for a sn (student number), inside an array of sorted structs named sr (student record)
    The student array of structs is global in this example, and the zero'th element of the array, is not used.

    Code:
    int Number_Search(int target) {     
       int low, mid, high;
       low = 1; high = Hi;
    
       while(!target) {
          printf("\n Enter the Student Number: ");
          scanf("&#37;d", &target);
       }
       while(low <= high) {
          mid = (low + high) / 2;
          if(sr[mid].sn == target) {         /* is it a match ? */
             PrintHeader();
             printf("\n  %5d   %-11s      %c   %2d   %-22s", sr[mid].sn,
             sr[mid].name, sr[mid].sex, sr[mid].age, sr[mid].major);
             return mid;
          } 
          else if(sr[mid].sn < target)      /* is our guess too high? */
    	      low = mid + 1;                 /* then increase the low point */
          else 
    	      high = mid - 1;                /* too low, so decrease high point */
       }  
       printf("\n No Match ");
       return 0;                            /* no match here */
    }

  9. #9
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    Quote Originally Posted by Adak View Post
    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
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    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
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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!
    Last edited by iMalc; 05-30-2008 at 03:17 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  13. #13
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    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
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  14. #14
    Registered User
    Join Date
    Apr 2008
    Posts
    15
    Code:
    #include<stdio.h>
    #include<conio.h>
    #define size 10
    void main()
    {
    	int arr[size],i,j,nLarge,nLast=size,nSpos,t;
    	printf("Enter Input Data..\n");
    	for(i=0;i<size;i++)
    	{
    		scanf("%d",&arr[i]);
    	}
    	printf("Sorted Data is : \n");
    	for(i=0;i<size;i++)
    	{
    		nSpos=0;
    		for(j=0;j<nLast;j++)   
    		{
    			if(arr[j]>arr[nSpos])
    			{
    				nLarge=arr[j];
    				nSpos=j;
    			}
    		}
    		t=arr[nLast-1];
    		arr[nLast-1]=arr[nSpos];
    		arr[nSpos]=t;
    		--nLast;
    	}
    	printf("\n\n");
    	for(i=0;i<size;i++)
    	{
    		printf("%d\n",arr[i]);
    	}
    	getch();
    }
    Hello...
    My Selection sort, what do you think?

  15. #15
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    Does it work?
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary search on strings
    By ckathy in forum C++ Programming
    Replies: 1
    Last Post: 10-02-2007, 06:25 PM
  2. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  3. Binary tree search efficiency
    By ExCoder01 in forum A Brief History of Cprogramming.com
    Replies: 8
    Last Post: 10-23-2003, 11:11 PM
  4. writing/reading from file produces double results.
    By stumon in forum C Programming
    Replies: 4
    Last Post: 03-20-2003, 04:01 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21