0
int BinarySearch(int A[], int p, int r, int value)
{
    int q = (p + r) / 2;

    if (A[q] == value)
    {
        return q;   //value found
    }
    if (p == q) 
    {
        return 0;   //not found
    }
    if (A[q] > value)
    {
        return BinarySearch(A, p, q, value);
    }
    else
    {
        return BinarySearch(A, q + 1, r, value); 
    }
} //binary search ends here

Now, the problem is that whenever I want to search the last element of an array, this code gives an error. can anyone please explain why?

chrk
  • 4,037
  • 2
  • 39
  • 47
sunki08
  • 31
  • 1
  • 1
  • 6
  • This [works well on ideone](http://ideone.com/9NLYIj). Could you provide a set of data for which your code fails? – Sergey Kalinichenko Apr 30 '14 at 10:25
  • ok the problem is solved i should have written second if condition which checks p==q at the end now it's working properly .By the way any suggestion to improve this code will be appreciated. – sunki08 Apr 30 '14 at 10:25
  • @ dasblinkenlight i am using dev c++ ide and entered an array of 1 2 3 4 5 and checked for 5 it said not found – sunki08 Apr 30 '14 at 10:26
  • still there is an error in my code .it will behave abnormally if i want to search a value that is not in the array but solution provided by LearningC is correct. Thank you – sunki08 Apr 30 '14 at 11:01

1 Answers1

0

Make the search end case based on first index p and last index r,

int BinarySearch(int A[], int p, int r, int value)
{
    int q = (p + r) / 2;
    if( p > r )
    {
      return 0;
    }
    if (A[q] == value)
    {
        return q;   //value found
    }
    if (A[q] > value)
    {
        return BinarySearch(A, p, q-1, value);
    }
    else
    {
        return BinarySearch(A, q + 1, r, value); 
    }
}
LearningC
  • 3,182
  • 1
  • 12
  • 19
  • hello LearningC ,can you please explain how to get its time complexity ? – sunki08 May 01 '14 at 05:07
  • @sunki08 ok. read these [link1](http://stackoverflow.com/questions/8185079/how-to-calculate-binary-search-complexity) and [link2](http://stackoverflow.com/questions/6094864/how-do-you-calculate-the-big-oh-of-the-binary-search-algorithm). search for time complexity of binary search you'll get many links about deriving time complexity. – LearningC May 01 '14 at 09:34