4

Let's say we want to write a function in C that finds a specified target value in an unsorted array of ints. In general, this is simple and runs in O(n) time:

int search(int *data, int len, int target)
{
    int i;
    for(i = 0; i < len; i++)
        if(data[i]==target) return i;
    return -1;
}

Let's say we're being masochistic and want to approach this with a divide and conquer algorithm instead. We'll run into trouble on the recursive part because we can't exclude half the array each time, like we can with binary search:

int search(int *data, int start, int stop, int target)
{
// Base case: we've divided the array into two size subarray
    if(stop==start+1)
{
    if(data[start]==target) return start;
    if(data[stop]==target) return stop;
    return -1;
}
/* The recursion part is tricky.  
    We *need* to parse both halves of the array, because we can't safely
    exclude any part of the array; it's not sorted, so we can't predict
    which half it's going to be in.*/
else
{
    /** This obviously doesn't work. */
    int mid = (stop-start)/2;
    return search(data, start, mid, target);
    return search(data, mid+1, stop, target);
}
}

Is there any way to make this work?

NOTE: This is not asking people to do my homework for me, as some of you may think when reading this question. It is, however, inspired by curiosity after I encountered this problem when trying to solve a question in an assignment that I've submitted earlier this week.

Improve this question
2
  • 1
    not sure if I understand the question, because it seems so simple int sts = search(data,start,mid,targte); if (sts == -1) return search(data,mid+1,stop,target); else return sts; Commented Nov 7, 2013 at 9:10
  • Use int mid=start+1 - the degenerate case of divide-and-conquer. Commented Nov 7, 2013 at 9:15

3 Answers 3

Reset to default
2

I think the answer to your question is no, you can't achieve any benefit using the binary split approach if the data is unsorted.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Specifically, if the data is unsorted, there exists no algorithm that will let you find the location of a given element in less than O(n) time.
@interjay: the question was "Is there any way to make this work?", the answer is "no"
Actually you can achieve benefit by binary range splitting if your search is multithreaded. How much you gain on a simple 'int' equality search versus the added complexity is another matter. With a more complex search criteria then the OP (for example find a prime among them) it can give you real benefits.
1

How about changing the recursive call to:

else
{
    int mid = (stop-start)/2;
    int x = search(data, start, mid, target);
    if (x == -1)
        return search(data, mid+1, stop, target);
    else 
        return x;
}
Improve this answer

Comments

1

If the data are not sorted you can not use binary search. But divide and conquer can be used with the following recursive logic (linear search):

int search(int *data, int len, int target)
{
    if (len == 0)
        return -1;
    else if (data[0] == target);
        return 0;
    else
        return 1 + search(++data, len-1, target);
}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.