Binary Search: Algorithms

Binary Search: Algorithms

What is Binary Search?

Binary Search is an interval searching algorithm used to search for an item in the sorted list. It works by repeatedly dividing the list into two equal parts and then searching for the item that is the part where it can possibly exist.

Unlike linear search, there are a few conditions for applying binary search:

1. The list must be sorted.
2. Random access to the list member.

It means that we cannot apply the binary search in unsorted or liked data structures.

Visualization of Binary Search:

Algorithm for Binary Search in C

Let [X] be the element we are searching for, and the array is sorted in the ascending order.

1. Compare [X] with the middle element of the array.
    
2. If [X] matches with the middle element, we return the index of the middle element.
    
3. Else if [X] is greater than the middle element, it means that [X]
    can only lie in the right half subarray after the middle element. So, we repeat steps 1 and 2 for the right half subarray and leave the left half subarray from the algorithm
    
4. Else if [X] is smaller than the middle element, it means that [X]
    can only lie in the left half subarray before the middle element. So, we repeat steps 1 and 2 for the left half subarray.
    
5. We will keep doing that till we find [X] or there is no element left in the subarray being considered.

As we can see, the binary search ignores the half elements of the subarray after each pass. Due to this, it is able to reduce the time required for searching the element in the array as compared to linear search.

#include<stdio.h>

int binarySearch(int *arr, int size, int key){

    int start = 0;

    int end = size - 1;

    int mid = start+(end-start)/2;

   

    while (start <= end){

        if (arr[mid] == key){

            return mid;

        }

        if (key > arr[mid]){

            start = mid+1;

        }

        else{

            end = mid-1;

        }

        mid = start+(end-start)/2;

    }

    return -1;

}

int main(){

    int size,k;

    printf("Enter Size Of Array: ");

    scanf("%d",&size);

   

    int arr[size];

    printf("Enter Array Elements: ");

    for(int i=0;i<size;i++)

    {

        scanf("%d",&arr[i]);

    }

    printf("Enter Number To Find: ");

    scanf("%d",&k);

    int result = binarySearch(arr,size,k);

    printf("\n%d Found at Index: %d",k,result);

    return 0;

}

Output: 

Complexity Analysis of Binary Search (Iterative)

Time Complexity: O(log n), where n is the number of elements in the array.
Auxiliary Space: O(1)