Разделить и захватить бинарный поиск в C

Question

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

#include <stdio.h>
#include "BinarySearch.h"

int main () {
    int a[] = {0,1,2,3,4,5,6,7,8,9};
    int index = binarySearch(a, 0, 9, 7);
    printf("%i", index);

    return 0;
}

int binarySearch (int* A, int first, int last, int key) {
    if (last < first)
        return -1;
    else {
        int mid = (last + first) / 2;

        if (A[mid] == key)
            return mid;

        int x, y;
        x = binarySearch(A, first, mid - 1, key);
        y = binarySearch(A, mid + 1, last, key);

        if (x == -1 && y == -1)
            return -1;
        else if (x == -1 && y != -1)
            return y;
        else
            return x;
    }
}

Answer 1

Это просто, 99 не существует в вашем массиве. Результат верный. Вы, вероятно, только что испортили параметры - первый - это массив, следующие два представляют диапазон поиска, а четвертый - то, что вы ищете. Правильный вызов будет:

int index = binarySearch(A, 0, 10, 4);

Кроме того, это

int* A = &a[0];

бесполезно, вы можете просто использовать a как массивы распадаются на указатели:

int index = binarySearch(a, 0, 7, 99);  // a instead of A

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

Что вы делаете O(n)в отличие от O(log(n)) бинарное решение поиска.

Answer 2

Для тех, кто все еще ищет решения, я нашел этоankzcode,

Он находит минимальное значение в массиве без линейного поиска, используя разделяй и властвуй.

#include <stdio.h>

int findMin(int a[], int l,int h)
{
    int pivot = (l + h) / 2;
    int minl=-1, minh = -1;

    if ( (pivot - l ) > 1) 
    {
        minl = findMin(a, l, pivot);
    }
    else 
    {
        minl = (a[l] > a[pivot])?a[pivot]:a[l];
    }
    if ( (h - pivot ) > 1) 
    {
        minh = findMin(a, pivot, h);
    }
    else 
    {
        minh = (a[l] > a[pivot])?a[pivot]:a[l];
    }

    return (minl>minh)?minh:minl;
}

int main()
{
    int a[]={5,2,9,10,3};
    printf("%d\n",findMin(a, 0, 5));
    return 0;
}

Answer 3

Вы дали ключ 99, которого нет в массиве, поэтому очевидно, что код возврата -1.