0

I am trying to implement the Binary Search algo from pset3, in O(log n) time. I keep getting stuck on implementing a recursive search that looks at just half the array to the right or to the left. That is without changing the input arguments for search

I made a slight variation where I store either the left or right array into a new array (which would make this O(nlogn) i guess) and it works.

How do you can you search just the left or right side without doing this?

bool search(int value, int values[], int n)
{
    // non-positive value of n
    if (n <= 0)
    {
       return false;   
    }

    // perform Binary Search Algo
   int mid = (n/2)-1, mid_val = values[mid];
   //printf("\nmid value: %i, mid: %i, value: %i, size:%i\n", mid_val, mid, value, n);

   if (mid_val == value)
   {
       return true;
   }
   else if (value > mid_val)
   {

       // create new array 
       int size = n - mid, temp[size];
       for (int i = mid + 1, j = 0; i < n; i++, j++)
       {
           temp[j] = values[i];
       }

       return search(value, temp, size);
   }
   else if (value < mid_val)
   {
       int size = n - mid, temp[size];
       for (int i = mid-1, j = 0; i >= 0; i--, j++)
       {
           temp[j] = values[i];
       }
       return search(value, temp, size);
   }

   return false;

}

1

Instead of providing an answer, how about a couple of big hints instead. First, there's no need to create a new array that duplicates values. Second, are you aware that you can recursively call search() using an element of the existing array as the starting point of the part of the array to be searched? It will be treated as element 0 in the next call.

   return search(value, values[<a number or variable goes here>], size);

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .