CODEWITHSUNDEEP
crecursionbinary-searchdivide-and-conquer
hakuna matata
hakuna matata

Reputation: 3327

divide and conque binary search in C

I'm trying to make a divide and conquer version of binary search, but one that divides the array to two subarrays and search similar to merging in merge sort, the reason I want to do that becuase I want to use it in cilk, but I have to make it that way. Here is the code I wrote, which seems to have something wrong with it as its returning -1 to valid key values.

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

Upvotes: 0

Views: 8485

Answers (3)

Ankzz
Ankzz

Reputation: 19

For any one still looking for solutions, I found this made by ankzcode.

It finds the minimum value in an array without linear search, using divide and 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;
}

Upvotes: 1

Luchian Grigore
Luchian Grigore

Reputation: 258648

It's simple, 99 doesn't exist in your array. The result is correct. You probably just messed up the parameters - the first one is the array, the next two represent the range of the search, the fourth one is what you're looking for. A correct call would be:

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

Also, this

int* A = &a[0];

is useless, you can simply use a as arrays decay to pointers:

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

Also - a binary search takes into account the fact that the array is sorted. If your key is lower than the middle value, why bother searching to the right - it's guaranteed you won't find it there.

What you're doing is O(n), as opposed to a O(log(n)) binary search solution.

Upvotes: 3

jiten
jiten

Reputation: 5264

you gave the key 99,which is not in array,So its obvious the code return -1.

Upvotes: 0

Related Questions