binary search

This is a discussion on binary search within the C Programming forums, part of the General Programming Boards category; I am really not good with recursion and I have never done it in C, so I thought I should ...

  1. #1
    Registered User
    Join Date
    Jun 2009
    Posts
    457

    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?

  2. #2
    Registered User
    Join Date
    Jun 2009
    Posts
    457
    Haha never mind, found it - I had my recursive calls backwards - I was searching the wrong half of the array each time

  3. #3
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    Glad it works for you but check out this thread. You will see how your binary search can be improved.

    help wiv encryption

  4. #4
    Registered User
    Join Date
    Jun 2009
    Posts
    457
    Interesting - the only reason I wrote this was to start getting a feel for recursion in C though.

  5. #5
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    Gotcha!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 05:15 PM
  2. deleting all nodes of a binary search tree...
    By sachitha in forum C++ Programming
    Replies: 3
    Last Post: 09-29-2004, 07:19 AM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

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