Solution:
Binary search only works on sorted array.
Calculate middle location of array and check the element which element to be searched.
Since array is sorted, if mid element is less then search item, then element is bound to be in the second half of list. In next steps, search within the respective part of the list
Start marker of array become middle +1 location, end remains same.
start= mid+1
Otherwise if the mid element is greater than search item, then element will be in the first half of list.
End marker of array become middle -1 location, start remains same.
Complexity: O(N/2)
#include <stdio.h>
int binarySearch(int array[],int start,int end,int search) {
if( start > end) {
// A base condition
// Happens when list does not contain value
return -1;
}
int mid = (int) ((start + end)/2);
if( array[mid] > search) {
binarySearch(array, start, mid-1, search);
}
else if ( array[mid] < search) {
binarySearch(array, mid+1, end, search);
}
else {
// A Base condition
// Element found, return its position
return mid+1;
}
}
int main() {
int arr[] = {1,5,6,10,19,31,72};
int size = sizeof(arr)/sizeof(arr[0]);
int pos = -1;
int searchItem = 1;
pos = binarySearch(arr, 0, 5,searchItem);
if(pos == -1) {
printf("%d not found in list",searchItem);
}
else {
printf("%d found at location %d",searchItem,pos);
}
return 0;
}
Output:
1 found at location 1
