Recursive binary search algorithm

[coolProgramer5]

Hi I trying to write a recursive binary search function. The program was is almost done however, when i attempted to make the program recursive it crashed.

#include <stdio.h>   /*librarys */
#include "simpio.h"

#define size 8

void BubbleSort(int num[]);  /* prototypes */
int binsearch (int val, int num[]);
int main()
{
    int num[size];
    printf("Enter 8 integers for the array 'num[]'\n");
    for (int j=0; j< size; j++)
    {
          num[j] = GetInteger();
    }
    printf("Enter an integer to be searched\n");
    int val=GetInteger();
    BubbleSort(num); 
    binsearch(val, num);  
    getchar();        
    return 0;
}
void BubbleSort(int num[])
{
      int i, j, flag = 1;    // set flag to 1 to start first pass
      int temp;             // holding variable
      for(i = 1; (i <= size) && flag; i++)
     {
          flag = 0;
          for (j=0; j < (size -1); j++)
         {
               if (num[j+1] < num[j])      // ascending order simply changes to <
              { 
                    temp = num[j];             // swap elements
                    num[j] = num[j+1];
                    num[j+1] = temp;
                    flag = 1;               // indicates that a swap occurred.
               }
          }
     }
     printf("\n\n");
     for(j=0; j<size; j++)
     {
              printf("%d ", num[j]);
     }
}
int binsearch (int val, int num[])
{
    int low, high, mid;
    low=0;
    high=size-1;
    while (low <= high)
    {
          mid=(low+high)/2;
          if (val < num[mid])
          {
             high=mid-1;
          }
          else if (val > num[mid])
          {
               low=mid+1;
          }
          else /* a match is found */
          {    
           return (binsearch(val, num)); // i think this is where the problem is
          }
    }
    return (-1);
} 

[jsmith]

Your program is infinitely recursive.

Think about the problem.

If the midpoint value is less than what you're looking for, then you need to look in the right half.
If the midpoint value is greater than what you're looking for, then you need to look in the left half.
Both of the above statements imply recursion, since they are performing the same logic, just on
a smaller piece of the array.

[coolProgramer5]

I'm sorry but I'm not sure i know what your talking about. Please clarify. Thanks.

[tummychow]

It means that it never stops repeating; that there is no condition that prevents the function from calling itself again.

[coolProgramer5]

I apologize I have been busy for a while. Anyways I am still having some troubles with the recursive binary algorithm The good news is that the program no longer crashes it just doesn't print out the answer.

/* this program sorts the integer array num
* then the program gets an integer to be searched
* if found the program prints out the location it first found in */

#include <stdio.h>   /*librarys */
#include "simpio.h"

#define size 8

void BubbleSort(int num[]);  /* prototypes */
int binsearch (int val, int num[]);
int main()
{
    int num[size];
    printf("Enter 8 integers for the array 'num[]'\n");
    for (int j=0; j< size; j++)
    {
          num[j] = GetInteger();
    }
    printf("Enter an integer to be searched\n");
    int val=GetInteger();
    BubbleSort(num); 
    binsearch(val, num);  
    getchar();        
    return 0;
}
void BubbleSort(int num[])
{
      int i, j, flag = 1;    // set flag to 1 to start first pass
      int temp;             // holding variable
      for(i = 1; (i <= size) && flag; i++)
     {
          flag = 0;
          for (j=0; j < (size -1); j++)
         {
               if (num[j+1] < num[j])      // ascending order simply changes to <
              { 
                    temp = num[j];             // swap elements
                    num[j] = num[j+1];
                    num[j+1] = temp;
                    flag = 1;               // indicates that a swap occurred.
               }
          }
     }
     printf("\n\n");
     for(j=0; j<size; j++)
     {
              printf("%d ", num[j]);
     }
}
int binsearch (int val, int num[])
{
    int result;
    int low, high, mid;
    low=0;
    high=size-1;
    while (low <= high)
    {
          mid=(low+high)/2;
          if (val < num[mid])
          {
             high=mid;
          }
         else if (val > num[mid])
          {
               low=mid;
          }
         else if (val==num[mid]) /* a match is found */
          {
               result=binsearch(val, num);
               printf("\nA match was found for '%d'\n", val);
               return (0);
               break;
          }
          else
          {
              printf("\nNo match was found for '%d'\n", val);
              break;
              return (-1);
          }
    }
    return 0;
}

[coolProgramer5]

Please help.

[jsmith]

Your program is infinitely recursive.

Think about the problem.

If the midpoint value is less than what you're looking for, then you need to look in the right half.
If the midpoint value is greater than what you're looking for, then you need to look in the left half.
Both of the above statements imply recursion, since they are performing the same logic, just on
a smaller piece of the array.

Everything I said above still applies.

Read the quote. I gave you the algorithm you need for binsearch(). There is no "while"
in the algorithm, and there are only essentially three if cases: the two above, and the
third one for the exact match. In your code, you have four cases: one for less than,
one for greater than, one for equal to, and the fourth one I have no idea how you
hit since the previous three cover all the possibilities.

Also, look at your code: If you find an exact match, you call binsearch() again, with
the same parameters as you called it with originally, so it will simply do the same
thing again, and find the same match, and then call itself again, and so forth.

[coolProgramer5]

I'm really sorry but i'm still a newbie so i don't quite understand what your trying to tell me. The program now prints something out but it always says that the number being searched isn't in the array even when it is.

/* this program sorts the integer array num
* then the program gets an integer to be searched
* if found the program prints out the location it first found in */

#include <stdio.h>   /*librarys */
#include "simpio.h"

#define size 8

void BubbleSort(int num[]);  /* prototypes */
void binary (int num[]);
int main()
{
    int num[size];
    int result;
    printf("Enter 8 integers for the array 'num[]'\n");
    for (int j=0; j< size; j++)
    {
          num[j] = GetInteger();
    }
    BubbleSort(num); 
    binary(num);  
    getchar();        
    return 0;
}
void BubbleSort(int num[])
{
      int i, j, flag = 1;    // set flag to 1 to start first pass
      int temp;             // holding variable
      for(i = 1; (i <= size) && flag; i++)
     {
          flag = 0;
          for (j=0; j < (size -1); j++)
         {
               if (num[j+1] < num[j])      // ascending order simply changes to <
              { 
                    temp = num[j];             // swap elements
                    num[j] = num[j+1];
                    num[j+1] = temp;
                    flag = 1;               // indicates that a swap occurred.
               }
          }
     }
     printf("\n\n");
     for(j=0; j<size; j++)
     {
              printf("%d ", num[j]);
     }
}
void binary (int num[])
{
    int result;
    printf("\nEnter an integer to be searched: ");
    int val=GetInteger();
    int low, high, mid;
    low=0;
    high=size-1; 
    if (low <= high)
    {
          mid=(low+high)/2;
          if (val < num[mid])
          {
             high=mid;
          }
         else if (val > num[mid])
          {
               low=mid;
          }
         else /* a match is found */
          {
               binary(num);
               printf("\nThe value %d occurs in the array in index %d.", val, mid);
          }
    }
    printf("\nThe value %d was not found.\n", val);
}

[coolProgramer5]

I figured out the program. Thanks

[jsmith]

Ok, so in that case:

If the midpoint value is less than what you're looking for, then you need to look in the right half.
If the midpoint value is greater than what you're looking for, then you need to look in the left half.
Both of the above statements imply recursion, since they are performing the same logic, just on
a smaller piece of the array.

// Search for 'target' in the array 'num', looking only at indices
// first...last inclusive.
bool binary_search( int num[], int first, int last, int target ) {
     int midpoint_index = ( first + last ) / 2;

    // If the midpoint value is less than what you're looking for, 
    // then you need to look in the right half.
    if( num[ midpoint_index ] < target )
         return binary_search( num, midpoint_index + 1, last, target );

    // If the midpoint value is greater than what you're looking for, 
    // then you need to look in the left half.
    else if( num[ midpoint_index ] > target )
         return binary_search( num, first, midpoint_index - 1, target );

    // If it's not less than and not greater than, it must be equal to
    else
         return true; // found it
}

Now I'll warn you that I deliberately left a bug in the above code so you
don't submit it as is.

[coolProgramer5]

that's okay I already fixed my program. But thanks for helping.

[jsmith]

I just wanted to show you how to translate plain english into C++ code.