Thread: binary search

I am really not good with recursion and I have never done it in C, so I thought I should learn and started with a simple binary search algorithm. However, it is doing wierd things that will probably be immediately obvious to you guys, but I am at a loss. Here is my code

Code:

#include <stdio.h>
#include <stdlib.h>

int binarySearch(double *numbers, int low, int high, double searchNum)
{
  printf("%d\n",((low + high) / 2));
  double check = numbers[((low + high) / 2)];
  int index;
  
  if (low == high && check != searchNum)
  {
    return -1;
  }
  else if (check == searchNum)
  {
    index = ((low + high) / 2);
    printf("yes = %d\n",index);
    return index;
  }
  else if (check < searchNum)
  {
    index = binarySearch(numbers, low, ((low + high) / 2), searchNum);
    printf("no1 = %d\n",index);
    return index;
  }
  else if (check > searchNum)
  {
    index = binarySearch(numbers, ((low + high) / 2), high, searchNum);
    printf("no2 = %d\n",index);
    return index;
  }
}

int main()
{
  double *numbers;
  int i;
  double searchNum;
  numbers = (double *) malloc(10000 * sizeof(double));
  
  for (i = 0; i < 10000; i++)
  {
    numbers[i] = (double) i;
   // printf("%f\n",numbers[i]);
  }
  printf("Check for: ");
  scanf("%lf",&searchNum);
  i = binarySearch(numbers, 0, 9999, searchNum);
  printf("%d\n",i);
}

The algorithm populates an array of 10,000 numbers with the indices of each box cast into doubles, and asks for a number to search for.

Right now, when I search for something, the

Code:

  printf("%d\n",((low + high) / 2));

line prints 9998 until it segfaults from the recursive overhead. Any hints?

Haha never mind, found it - I had my recursive calls backwards - I was searching the wrong half of the array each time

Glad it works for you but check out this thread. You will see how your binary search can be improved.

help wiv encryption

Interesting - the only reason I wrote this was to start getting a feel for recursion in C though.

Gotcha!