Алгоритм поиска рекурсивного несортированного массива в C?

Question

Допустим, мы хотим написать функцию на C, которая находит указанное целевое значение в несортированном массиве целых чисел. В общем, это просто и выполняется за O(n) раз:

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

Допустим, мы мазохистки и хотим подойти к этому с помощью алгоритма "разделяй и властвуй". Мы столкнемся с проблемами в рекурсивной части, потому что мы не можем исключать половину массива каждый раз, как мы можем с бинарным поиском:

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

Есть ли способ сделать эту работу?

ПРИМЕЧАНИЕ: здесь не просят людей делать за меня домашнее задание, как некоторые из вас могут подумать, читая этот вопрос. Это, однако, вдохновлено любопытством после того, как я столкнулся с этой проблемой, пытаясь решить вопрос в задании, которое я представил ранее на этой неделе.

Answer 1

Как насчет изменения рекурсивного вызова на:

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

Answer 2

Я думаю, что ответ на ваш вопрос - нет, вы не можете получить какую-либо выгоду, используя двоичный подход, если данные не отсортированы.

Answer 3

Если данные не отсортированы, вы не можете использовать бинарный поиск. Но "разделяй и властвуй" можно использовать со следующей рекурсивной логикой (линейный поиск):

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