CODEWITHSUNDEEP
carraysalgorithmrecursiondivide-and-conquer
Govind Parmar
Govind Parmar

Reputation: 21572

Recursive unsorted array search algorithm in C?

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.

Upvotes: 4

Views: 3805

Answers (3)

nikpel7
nikpel7

Reputation: 686

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);
}

Upvotes: 1

Ron Teller
Ron Teller

Reputation: 1890

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;
}

Upvotes: 1

Spalteer
Spalteer

Reputation: 484

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.

Upvotes: 2

Related Questions