#include <stdio.h>
// Recursive implementation of Binary Search Algorithm to return
// the position of target x in the sub-array A[low..high]
int binarySearch(int A[], int low, int high, int x)
{
// Base condition (search space is exhausted)
if (low > high)
return -1;
// we find the mid value in the search space and
// compares it with target value
int mid = (low + high)/2; // overflow can happen
// int mid = low + (high - low)/2;
// Base condition (target value is found)
if (x == A[mid])
return mid;
// discard all elements in the right search space
// including the mid element
else if (x < A[mid])
return binarySearch(A, low, mid - 1, x);
// discard all elements in the left search space
// including the mid element
else
return binarySearch(A, mid + 1, high, x);
}
// Recursive implementation of Binary Search Algorithm
int main(void)
{
int A[] = { 2, 5, 6, 8, 9, 10 };
int target = 5;
int n = sizeof(A)/sizeof(A[0]);
int low = 0, high = n - 1;
int index = binarySearch(A, low, high, target);
if (index != -1)
printf("Element found at index %d", index
); else
printf("Element not found in the array");
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CgovLyBSZWN1cnNpdmUgaW1wbGVtZW50YXRpb24gb2YgQmluYXJ5IFNlYXJjaCBBbGdvcml0aG0gdG8gcmV0dXJuCi8vIHRoZSBwb3NpdGlvbiBvZiB0YXJnZXQgeCBpbiB0aGUgc3ViLWFycmF5IEFbbG93Li5oaWdoXQppbnQgYmluYXJ5U2VhcmNoKGludCBBW10sIGludCBsb3csIGludCBoaWdoLCBpbnQgeCkKewogICAgLy8gQmFzZSBjb25kaXRpb24gKHNlYXJjaCBzcGFjZSBpcyBleGhhdXN0ZWQpCiAgICBpZiAobG93ID4gaGlnaCkKICAgICAgICByZXR1cm4gLTE7CgogICAgLy8gd2UgZmluZCB0aGUgbWlkIHZhbHVlIGluIHRoZSBzZWFyY2ggc3BhY2UgYW5kCiAgICAvLyBjb21wYXJlcyBpdCB3aXRoIHRhcmdldCB2YWx1ZQoKICAgIGludCBtaWQgPSAobG93ICsgaGlnaCkvMjsgICAgLy8gb3ZlcmZsb3cgY2FuIGhhcHBlbgogICAgLy8gaW50IG1pZCA9IGxvdyArIChoaWdoIC0gbG93KS8yOwoKICAgIC8vIEJhc2UgY29uZGl0aW9uICh0YXJnZXQgdmFsdWUgaXMgZm91bmQpCiAgICBpZiAoeCA9PSBBW21pZF0pCiAgICAgICAgcmV0dXJuIG1pZDsKCiAgICAvLyBkaXNjYXJkIGFsbCBlbGVtZW50cyBpbiB0aGUgcmlnaHQgc2VhcmNoIHNwYWNlCiAgICAvLyBpbmNsdWRpbmcgdGhlIG1pZCBlbGVtZW50CiAgICBlbHNlIGlmICh4IDwgQVttaWRdKQogICAgICAgIHJldHVybiBiaW5hcnlTZWFyY2goQSwgbG93LCAgbWlkIC0gMSwgeCk7CgogICAgLy8gZGlzY2FyZCBhbGwgZWxlbWVudHMgaW4gdGhlIGxlZnQgc2VhcmNoIHNwYWNlCiAgICAvLyBpbmNsdWRpbmcgdGhlIG1pZCBlbGVtZW50CiAgICBlbHNlCiAgICAgICAgcmV0dXJuIGJpbmFyeVNlYXJjaChBLCBtaWQgKyAxLCAgaGlnaCwgeCk7Cn0KCi8vIFJlY3Vyc2l2ZSBpbXBsZW1lbnRhdGlvbiBvZiBCaW5hcnkgU2VhcmNoIEFsZ29yaXRobQppbnQgbWFpbih2b2lkKQp7CiAgICBpbnQgQVtdID0geyAyLCA1LCA2LCA4LCA5LCAxMCB9OwogICAgaW50IHRhcmdldCA9IDU7CgogICAgaW50IG4gPSBzaXplb2YoQSkvc2l6ZW9mKEFbMF0pOwoKICAgIGludCBsb3cgPSAwLCBoaWdoID0gbiAtIDE7CiAgICBpbnQgaW5kZXggPSBiaW5hcnlTZWFyY2goQSwgbG93LCBoaWdoLCB0YXJnZXQpOwoKICAgIGlmIChpbmRleCAhPSAtMSkKICAgICAgICBwcmludGYoIkVsZW1lbnQgZm91bmQgYXQgaW5kZXggJWQiLCBpbmRleCk7CiAgICBlbHNlCiAgICAgICAgcHJpbnRmKCJFbGVtZW50IG5vdCBmb3VuZCBpbiB0aGUgYXJyYXkiKTsKCiAgICByZXR1cm4gMDsKfQ==