#include <stdio.h>
 
int binarySearch(int array[], int x, int low, int high) {
  while (low <= high) {
    int mid = low + (high - low) / 2;
 
    if (array[mid] == x)
      return mid;
 
    if (array[mid] < x)
      low = mid + 1;
 
    else
      high = mid - 1;
  }
 
  return -1;
}
 
int main(void) {
  int array[] = {3, 4, 5, 6, 7, 8, 9};
  int n = sizeof(array) / sizeof(array[0]);
  int x = 4;
  int result = binarySearch(array, x, 0, n - 1);
  if (result == -1)
    printf("Not found");
  else
    printf("Element is found at index %d", result);
  return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CgppbnQgYmluYXJ5U2VhcmNoKGludCBhcnJheVtdLCBpbnQgeCwgaW50IGxvdywgaW50IGhpZ2gpIHsKICB3aGlsZSAobG93IDw9IGhpZ2gpIHsKICAgIGludCBtaWQgPSBsb3cgKyAoaGlnaCAtIGxvdykgLyAyOwoKICAgIGlmIChhcnJheVttaWRdID09IHgpCiAgICAgIHJldHVybiBtaWQ7CgogICAgaWYgKGFycmF5W21pZF0gPCB4KQogICAgICBsb3cgPSBtaWQgKyAxOwoKICAgIGVsc2UKICAgICAgaGlnaCA9IG1pZCAtIDE7CiAgfQoKICByZXR1cm4gLTE7Cn0KCmludCBtYWluKHZvaWQpIHsKICBpbnQgYXJyYXlbXSA9IHszLCA0LCA1LCA2LCA3LCA4LCA5fTsKICBpbnQgbiA9IHNpemVvZihhcnJheSkgLyBzaXplb2YoYXJyYXlbMF0pOwogIGludCB4ID0gNDsKICBpbnQgcmVzdWx0ID0gYmluYXJ5U2VhcmNoKGFycmF5LCB4LCAwLCBuIC0gMSk7CiAgaWYgKHJlc3VsdCA9PSAtMSkKICAgIHByaW50ZigiTm90IGZvdW5kIik7CiAgZWxzZQogICAgcHJpbnRmKCJFbGVtZW50IGlzIGZvdW5kIGF0IGluZGV4ICVkIiwgcmVzdWx0KTsKICByZXR1cm4gMDsKfQ==