// C program to implement recursive Binary Search
// Made changes to original code from: https://www.geeksforgeeks.org/binary-search/
#include <stdio.h>
int j = 0; //variable to count number of "probes"
int binarySearch(int arr[], int l, int r) {
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == 1 && (mid-1)>=0 && arr[mid-1] == 0){
printf("The required min index is %d and the no. of probes is %d\n",mid,j);
return 0;
}
if (arr[mid] == 1 && (mid-1)>=0 && arr[mid-1] == 1){
j = j + 1;
return binarySearch(arr, l, mid - 1);
}
j = j + 1;
return binarySearch(arr, mid + 1, r);
}
printf("Smallest index i not found and the number of probes is %d\n",j);
return -1;
}
int main(void)
{
int arr[] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 };
int n = sizeof(arr) / sizeof(arr[0]);
//Case: No smallest index
j = 0; //Initializing no. of probes to 0
binarySearch(arr, 0, n - 1);
int arr1[] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1 };
n = sizeof(arr1) / sizeof(arr1[0]);
//Case: the required min index is 30
j = 0; //Initializing no. of probes to 0
binarySearch(arr1, 0, n - 1);
return 0;
}
