#include <stdio.h>
// Iterative implementation of Binary Search Algorithm to return
// the position of target x in the array A of size N
int binarySearch(int A[], int N, int x)
{
// search space is A[low..high]
int low = 0, high = N - 1;
// iterate till search space contains at-least one element
while (low <= high)
{
// 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;
// int mid = high - (high - low)/2;
// target value is found
if (x == A[mid])
return mid;
// if target is less than the mid element, discard all elements
// in the right search space including the mid element
else if (x < A[mid])
high = mid - 1;
// if target is more than the mid element, discard all elements
// in the left search space including the mid element
else
low = mid + 1;
}
// target doesn't exist in the array
return -1;
}
// Iterative 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 index = binarySearch(A, n, target);
if (index != -1)
printf("Element found at index %d", index
); else
printf("Element not found in the array");
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CgovLyBJdGVyYXRpdmUgaW1wbGVtZW50YXRpb24gb2YgQmluYXJ5IFNlYXJjaCBBbGdvcml0aG0gdG8gcmV0dXJuCi8vIHRoZSBwb3NpdGlvbiBvZiB0YXJnZXQgeCBpbiB0aGUgYXJyYXkgQSBvZiBzaXplIE4KaW50IGJpbmFyeVNlYXJjaChpbnQgQVtdLCBpbnQgTiwgaW50IHgpCnsKICAgIC8vIHNlYXJjaCBzcGFjZSBpcyBBW2xvdy4uaGlnaF0KICAgIGludCBsb3cgPSAwLCBoaWdoID0gTiAtIDE7CgogICAgLy8gaXRlcmF0ZSB0aWxsIHNlYXJjaCBzcGFjZSBjb250YWlucyBhdC1sZWFzdCBvbmUgZWxlbWVudAogICAgd2hpbGUgKGxvdyA8PSBoaWdoKQogICAgewogICAgICAgIC8vIGZpbmQgdGhlIG1pZCB2YWx1ZSBpbiB0aGUgc2VhcmNoIHNwYWNlIGFuZAogICAgICAgIC8vIGNvbXBhcmVzIGl0IHdpdGggdGFyZ2V0IHZhbHVlCgogICAgICAgIGludCBtaWQgPSAobG93ICsgaGlnaCkvMjsgICAgLy8gb3ZlcmZsb3cgY2FuIGhhcHBlbgogICAgICAgIC8vIGludCBtaWQgPSBsb3cgKyAoaGlnaCAtIGxvdykvMjsKICAgICAgICAvLyBpbnQgbWlkID0gaGlnaCAtIChoaWdoIC0gbG93KS8yOwoKICAgICAgICAvLyB0YXJnZXQgdmFsdWUgaXMgZm91bmQKICAgICAgICBpZiAoeCA9PSBBW21pZF0pCiAgICAgICAgICAgIHJldHVybiBtaWQ7CgogICAgICAgIC8vIGlmIHRhcmdldCBpcyBsZXNzIHRoYW4gdGhlIG1pZCBlbGVtZW50LCBkaXNjYXJkIGFsbCBlbGVtZW50cwogICAgICAgIC8vIGluIHRoZSByaWdodCBzZWFyY2ggc3BhY2UgaW5jbHVkaW5nIHRoZSBtaWQgZWxlbWVudAogICAgICAgIGVsc2UgaWYgKHggPCBBW21pZF0pCiAgICAgICAgICAgIGhpZ2ggPSBtaWQgLSAxOwoKICAgICAgICAvLyBpZiB0YXJnZXQgaXMgbW9yZSB0aGFuIHRoZSBtaWQgZWxlbWVudCwgZGlzY2FyZCBhbGwgZWxlbWVudHMKICAgICAgICAvLyBpbiB0aGUgbGVmdCBzZWFyY2ggc3BhY2UgaW5jbHVkaW5nIHRoZSBtaWQgZWxlbWVudAogICAgICAgIGVsc2UKICAgICAgICAgICAgbG93ID0gbWlkICsgMTsKICAgIH0KCiAgICAvLyB0YXJnZXQgZG9lc24ndCBleGlzdCBpbiB0aGUgYXJyYXkKICAgIHJldHVybiAtMTsKfQoKLy8gSXRlcmF0aXZlIGltcGxlbWVudGF0aW9uIG9mIEJpbmFyeSBTZWFyY2ggQWxnb3JpdGhtCmludCBtYWluKHZvaWQpCnsKICAgIGludCBBW10gPSB7IDIsIDUsIDYsIDgsIDksIDEwIH07CiAgICBpbnQgdGFyZ2V0ID0gNTsKCiAgICBpbnQgbiA9IHNpemVvZihBKS9zaXplb2YoQVswXSk7CiAgICBpbnQgaW5kZXggPSBiaW5hcnlTZWFyY2goQSwgbiwgdGFyZ2V0KTsKCiAgICBpZiAoaW5kZXggIT0gLTEpCiAgICAgICAgcHJpbnRmKCJFbGVtZW50IGZvdW5kIGF0IGluZGV4ICVkIiwgaW5kZXgpOwogICAgZWxzZQogICAgICAgIHByaW50ZigiRWxlbWVudCBub3QgZm91bmQgaW4gdGhlIGFycmF5Iik7CgogICAgcmV0dXJuIDA7Cn0=