I know that there is a function bsearch
present in stdlib.h
but still I want to implement this.
This is my code for binary search. Any and all reviews are welcome.
#include<stdio.h>
#include<stdlib.h>
int compare (const void * a, const void * b)
{
return (*(int*)a - *(int*)b);
}
int bin_search(int arr[], int min_index, int max_index, int element)
{
/*
Searches for an element in the array arr
Returns fist index of element if present else returns -1
*/
if (min_index > max_index){
return -1;
}
else
{
//Don't change this assignment of mid_point. It avoids overflow
int mid_point = min_index + (max_index - min_index)/2;
if (arr[mid_point] > element){
return bin_search(arr, min_index, mid_point - 1, element);
}
else if (arr[mid_point] < element){
return bin_search(arr, mid_point + 1, max_index, element);
}
else{
return mid_point;
}
}
}
int main()
{
int length;
while (1)
{
printf("Enter a positive length: ");
scanf("%d", &length);
if (length > 1){
break;
}
else{
printf("You entered length = %d\n\n", length);
}
}
int *arr = malloc(sizeof(int) * length);
if (arr == NULL)
{
perror("The following error occurred");
exit(-1);
}
for (int i = 0; i < length; i++){
scanf("%d", &arr[i]);
}
int element;
printf("\nEnter the element to be searched: ");
scanf("%d", &element);
qsort(arr, length, sizeof(int), compare);
int index = bin_search(arr, 0, length - 1, element);
if (index == -1){
printf("\nElement not in the array");
}
else{
printf("\nIndex of element is %d", index);
}
free(arr);
return 0;
}
Thanks to @Josay for pointing out an infinite loop that I didn't know about in the original code.
Updated Code after answer by William Morris
int bin_search(int arr[], int min_index, int max_index, int element)
{
/*
Searches for an element in the array arr
Returns index of element if present else returns -1
*/
if (min_index > max_index){
return -1;
}
//Don't change this assignment of mid_point. It avoids overflow
int mid_point = min_index + (max_index - min_index)/2;
if (arr[mid_point] > element){
return bin_search(arr, min_index + 1, mid_point, element);
}
else if (arr[mid_point] < element){
return bin_search(arr, mid_point, max_index - 1, element);
}
return mid_point;
}