Problem with Binary Search

[SHENGTON]

Hello, good day. :)

I got a problem with "passes occurred". This is the only problem left in my program. My program is about Naive Searching and Binary Searching. There's no problem with my "Naive Searching". The problem is the "Binary Searching".

Naive Searching: This is the result when I inputted a number to be searched in the array. There's no problem with the "passes". The "passes occurred" there is how many times does the searching occurred.

Since:
index --> 0 1 2 3 4
array --> 5 4 3 2 1
passes --> 1 2 3 4 5

[IMG]http://i168.photobucket.com/albums/u162/SHENGTON/naive.png[/IMG]

Binary Searching:

Since:
index --> 0 1 2 3 4
array --> 1 2 3 4 5
passes -->(How many times the array divided during searching)

Since I inputted "4" to be search, the passes occurred should be "2" only.

[IMG]http://i168.photobucket.com/albums/u162/SHENGTON/binary.png[/IMG]

NOTE: The numbers in the array will depend on what the user inputted in the "Input Items".

Here's my code:

#include<stdio.h>
#include<conio.h>
int naive(int a[], int size);
int binary(int a[],int size);
int display(int a[],int size);
int disp(int a[],int size);
void swap (int a[],int size);
void paws(int a[],int size);
int main()
{
 int a[100],cho=0,i,n;
 int pop=0;
 do
 {
  printf("\n\n\n [1] Input Items\n");
  printf(" [2] Naive Search\n");
  printf(" [3] Binary Search\n");
  printf(" [4] Display Items\n");
  printf(" [5] Exit\n\n");
  printf(" Enter your choice: ");
  scanf("%d",&cho);
  i = getchar();
  if(cho==1)
  {
   clrscr();
   printf("\n\n Enter integer for total numbers to be sorted: ");
   scanf("%d",&n);
   printf("\n\n");
   for(i=0;i<=n-1;i++)
   {
    printf(" Enter integer for no.%d : ",i+1);
    scanf("%d",&a[i]);
   }
   pop=1;
  }
  else if(cho==2 && pop)
  {
   naive(a,n);
  }
  else if(cho==3 && pop)
  {
   binary(a,n);
  }
  else if(cho==4 && pop)
  {
   display(a,n);
  }
  else
  {
   clrscr();
   printf("  _____________________\n |  \t\t       |");
   printf("\n | The array is empty. |\n");
   printf(" |_____________________|");
  }
 }
 while(cho != 5);
 {
  clrscr();
  printf("\n\n\n\n\n\n\n\n\n\n\n\n\t\t\t    ___________________\n\n\t\t\t    Press Enter to Exit\n");
  printf("\t\t\t    ___________________");
  i = getchar();
  ++i;
 }
 clrscr();
 return 0;
}


int display(int a[],int size)
{
 int i;
 clrscr();
 paws(a,size);
 printf("\n\n The array contains: ");
 for(i=0;i<size;i++)
 {
  printf("%3d",a[i]);
 }
}

int naive(int a[],int size)
{
 int i,n,found=0,index;
 clrscr();
 paws(a,size);
 display(a,size);
 printf("\n\n Enter the element to be searched: ");
 scanf("%d",&n);
 for(i=0;i<=size;i++)
 {
  if(n==a[i])
  {
   found=1;
   index=i;
  }
 }
 if(found==1)
 {
  printf("\n %d is found at index %d, %d passes occurred",n,index,index+1);
 }
 else
 {
  printf("\n %d is not found.",n);
 }
}

int binary(int a[],int size)
{
 int x,i,found=0,index,p;
 clrscr();
 swap(a,size);
 disp(a,size);
 printf("\n\n Enter the element to be searched: ");
 scanf("%d",&x);
 if(x==a[size/2])
 {
  for(i=size/2;i<size;i++)
  {
   if(x==a[i])
   {
    found=1;
    index=i;
   }
   else
   {
    p=1;
   }
  }
  if(found==1)
  {
   printf("\n %d is found at index %d, %d passes occurred.",x,index,p);
  }
  else
  {
   printf("\n %d is not found.",x);
  }
 }

 else if(x<a[size/2])
 {
  for(i=0;i<size/2;i++)
  {
   if(x==a[i])
   {
    found=1;
    index=i;
   }
   else
   {
    p=2;
    p++;
   }
  }
  if(found==1)
  {
   printf("\n %d is found at index %d, %d passes occurred.",x,index,p);
  }
  else
  {
   printf("\n %d is not found.",x);
  }
 }

 else if(x>a[size/2])
 {
  for(i=(size/2)+1;i<size;i++)
  {
   if(x==a[i])
   {
    found=1;
    index=i;
   }
   else
   {
    p=2;
    p++;
   }
  }
  if(found==1)
  {
   printf("\n %d is found at index %d, %d passes occurred.",x,index,p);
  }
  else
  {
   printf("\n %d is not found.",x);
  }
 }
}

void swap(int a[],int size)
{
 int i,j,t;
 for(i=0;i<size-1;i++)
 {
  for(j=i+1;j<size;j++)
  {
   if(a[i]>a[j])
   {
    t=a[j];
    a[j]=a[i];
    a[i]=t;
   }
  }
 }
}

void paws(int a[],int size)
{
 int i,j,t;
 for(i=0;i<size-1;i++)
 {
  for(j=i+1;j<size;j++)
  {
   if(a[i]<a[j])
   {
    t=a[j];
    a[j]=a[i];
    a[i]=t;
   }
  }
 }
}

int disp(int a[],int size)
{
 int i;
 clrscr();
 printf("\n\n The array contains: ");
 for(i=0;i<size;i++)
 {
  printf("%3d",a[i]);
 }
}

[Ancient Dragon]

Where in the world did you get that binary seach algorithm??? It isn't nearly that hard.

void bsearch(int a[], int size)
{
    int n = 0;
    int high,low,mid,count;
    printf("Enter number to be searched\n");
    scanf("%d", &n);
    getchar();
    high = size;
    low = 0;
    count = 0;
    do {
         mid = low + ((high - low) / 2);
        if( n > a[mid])
            low = mid+1;
        else if( n < a[mid] )
            high = mid-1;
        ++count;
    } while( a[mid] != n && low <= high);
    printf("count = %d\n", count);
    if( low > high )
        printf("%d not found\n", n);
    else
        printf("a[%d] = %d\n", mid, a[mid]);
}

[SHENGTON]

Hello Ancient Dragon,

Thanks for helping me Sir. I got this from here. It is in the "Code Snippets" -->Binary Search of an element in an array of elements

So does it mean that the code that I copied from is wrong?

Ok I'll try your code Sir.

[Ancient Dragon]

That's not binary search that I learned. looks more like linear search.

[SHENGTON]

What's the purpose of the "count" variable Sir?

[Ancient Dragon]

You said in your original post that you wanted to know the number of passes through the loop that it took to either find the number or determine that the number was not in the array. Otherwise the count variable can be deleted because it servers no other purpose.

[SHENGTON]

Hello Ancient Dragon,

Here's the complete code of Naive and Binary Searching. This code was checked and approved my instructor.

#include<stdio.h>
#include<conio.h>
int naive(int a[], int size);
int binary(int a[],int size);
int display(int a[],int size);
int disp(int a[],int size);
void swap (int a[],int size);
void paws(int a[],int size);
int main()
{
 int a[100],cho=0,i,n;
 int pop=0;
 do
 {
  printf("\n\n\n [1] Input Items\n");
  printf(" [2] Naive Search\n");
  printf(" [3] Binary Search\n");
  printf(" [4] Display Items\n");
  printf(" [5] Exit\n\n");
  printf(" Enter your choice: ");
  scanf("%d",&cho);
  i = getchar();
  if(cho==1)
  {
   clrscr();
   printf("\n\n Enter integer for total numbers to be sorted: ");
   scanf("%d",&n);
   printf("\n\n");
   for(i=0;i<=n-1;i++)
   {
    printf(" Enter integer for no.%d : ",i+1);
    scanf("%d",&a[i]);
   }
   pop=1;
  }
  else if(cho==2 && pop)
  {
   naive(a,n);
  }
  else if(cho==3 && pop)
  {
   binary(a,n);
  }
  else if(cho==4 && pop)
  {
   display(a,n);
  }
  else
  {
   clrscr();
   printf("  _____________________\n |  \t\t       |");
   printf("\n | The array is empty. |\n");
   printf(" |_____________________|");
  }
 }
 while(cho != 5);
 {
  clrscr();
  printf("\n\n\n\n\n\n\n\n\n\n\n\n\t\t\t    ___________________\n\n\t\t\t    Press Enter to Exit");
  printf("\n\t\t\t    ___________________");
  i = getchar();
  ++i;
 }
 clrscr();
 return 0;
}


int display(int a[],int size)
{
 int i;
 clrscr();
 paws(a,size);
 printf("\n\n The array contains: ");
 for(i=0;i<size;i++)
 {
  printf("%3d",a[i]);
 }
}

int naive(int a[],int size)
{
 int i,n,found=0,index;
 clrscr();
 paws(a,size);
 display(a,size);
 printf("\n\n Enter the number to be searched: ");
 scanf("%d",&n);
 for(i=0;i<=size;i++)
 {
  if(n==a[i])
  {
   found=1;
   index=i;
  }
 }
 if(found==1)
 {
  printf("\n %d is found at index %d, %d passes occurred",n,index,index+1);
 }
 else
 {
  printf("\n %d is not found.",n);
 }
}

int binary(int a[],int size)
{
 int n = 0;
 int high,low,i,index,pass;
 clrscr();
 swap(a,size);
 disp(a,size);
 printf("\n\n Enter number to be searched: ");
 scanf("%d",&n);
 getchar();
 high = size;
 low = 0;
 pass=0;
 do
 {
  i = low + ((high - low) / 2);
  if(n == a[i])
  {
   pass++;
  }
  else if(n > a[i])
  {
   low = i+1;
   pass++;
  }
  else if( n < a[i] )
  {
   high = i-1;
   pass++;
  }
 }
 while( a[i] != n && low <= high);
 {
  if( low > high )
  {
   printf("\n %d not found\n", n);
  }
  else
  {
   index=i;
   printf("\n %d is found at index %d, %d passes occurred.",n,index,pass);
  }
 }
}

void swap(int a[],int size)
{
 int i,j,t;
 for(i=0;i<size-1;i++)
 {
  for(j=i+1;j<size;j++)
  {
   if(a[i]>a[j])
   {
    t=a[j];
    a[j]=a[i];
    a[i]=t;
   }
  }
 }
}

void paws(int a[],int size)
{
 int i,j,t;
 for(i=0;i<size-1;i++)
 {
  for(j=i+1;j<size;j++)
  {
   if(a[i]<a[j])
   {
    t=a[j];
    a[j]=a[i];
    a[i]=t;
   }
  }
 }
}

int disp(int a[],int size)
{
 int i;
 clrscr();
 printf("\n\n The array contains: ");
 for(i=0;i<size;i++)
 {
  printf("%3d",a[i]);
 }
}

[Adak]

When you see code like this, why not simplify it?

if(n == a[i])
  {
   pass++;
  }
  else if(n > a[i])
  {
   low = i+1;
   pass++;
  }
  else if( n < a[i] )
  {
   high = i-1;
   pass++;
  }

to just:
  pass++;
  if(n == a[i])
  {
    return the i;
  }
  else if(n > a[i])
  {
   low = i+1;
  }
  else if( n < a[i] )
  {
   high = i-1;
  }

Shorter, simpler, and more clear.