Binary Search

Simple explanation and C code for this basic algorithm!

Binary Search is used to find elements in a sorted array. The time complexity of binary search is O(log n), which is faster than linear search’s time complexity of O(n).

Basic Principle

1. If the target value is less than the middle number, continue searching in the left half.
2. If the target value is more than the middle number , continue searching in the right half.
3. This continues till we get the middle number = target value (i.e target found) or the array runs out of elements (i.e target not found)

Algorithm

1. Find the element at arr[size/2], which will be the array’s midpoint. (The array is split halfway, with the lower half consisting of items 0 to midpoint -1 and the top half consisting of elements midpoint to size -1.)
2. Compare the key to arr[midpoint] by calling the user function.
3. If the key is a match, return arr[midpoint].
4. Otherwise return NULL, indicating that there is no match if the array has only one element.

5. if key < arr[midpoint] , call function to search lower half of array.

else call search recursively to search the upper half of the array.

C code!

// Binary Search
#include <stdio.h>

int binary(int a[], int lower,int upper, int target){
   int mid =( lower + upper)/2;
    
    if ( target == a[mid])
    {
        return mid;
    }
    else if(target > a[mid])
    {
        return binary(a ,mid, upper,target);
    }
    else if (target < a[mid])
    {
        return binary(a, lower, mid, target);
    }
    else printf("Target not found");
}

int main()
{
    int a[5] = { 1 ,4 ,5,7,8};
    printf("Position - %d", binary (a, 0, 4, 8));
    
}