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

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

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

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.

> 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

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.

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

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("%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 */
}

---

Quote:

---

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

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?

Does it work?

> Please check if it's right, i think i'm getting right output, but not sure...
Some cases to try
- an array with 0 elements
- an array with 1 element
- an array with an even number of elements
- an array with an odd number of elements
- an array with a power of 2 elements
- an array with a prime number of elements

Yes, it does work. But did I implement it right? I followed this animation tutorial :

http://www.cse.ust.hk/faculty/tcpong...ds/select.html

Quote:

---

Originally Posted by Todd Burch

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

---

You're right, though I intended it to be the number of items rather than the index of the last item. This one is even wrong in my source code. r should be assigned n-1 at the start. This showed up a hole in my unit tests and I'm fixing this now.
I found two other bugs too, by adding these extra unit tests! I'm not having a good day so far.