Разделить и бинарный поиск в 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

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

Answer 3

Для любого, кто еще ищет решения, I found this made by ankzcode.

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

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