Binary Search Using Divide and Conquer

Pseudo Code Algorithm for Binary Search.

This is a recursive implementation of a Binary Search algorithm using the Divide and Conquer technique. Binary Search is efficient for finding an element in a sorted array, with a time complexity of O(log⁡*n).

BinarySearch(array,low,high,key)//where key is the element to be searched
{
     if(low==high)
    if(a[low]==key)
     return low;
     else
     return -1;
}
else{
    mid=(low+high)/2
    if(key==array[mid])
    return mid;
    else if(key>array[mid])
    return BinarySearch(array,mid+1,high,key)
    else
    return BinarySearch(array,low,mid+1,key)
}
}

Explanation of Pseudo Code:

Function: BinarySearch(array, low, high, key)

Parameters:

• array: the sorted array where we are searching for an element.
• low: the starting index of the current search range.
• high: the ending index of the current search range.
• key: the element we want to find in the array.

Base Case:

(Check if low == high):

• If low equals high, then the search range has only one element.
• If array[low] == key, the function returns low, the index of key in the array.
• If array[low] != key, the function returns -1, meaning the element is not found.

1. Calculate Midpoint:
   • mid = (low + high) / 2: Calculate the middle index of the current search range.
2. Check if the Middle Element is the Key:
   • If array[mid] == key, the function returns mid, as we have found the key.
3. Divide and Conquer:
   • If key > array[mid]: The key must be in the right half of the array. The function recursively calls BinarySearch(array, mid + 1, high, key).
   • If key < array[mid]: The key must be in the left half of the array. The function recursively calls BinarySearch(array, low, mid - 1, key).

Recursive Binary Search Using Divide and Conquer in C.

#include <stdio.h>

void main(){
    int n,key;
    printf("ENTER THE NUMBER OF ELEMENTS:");
    scanf("%d",&n);
    int a[n];
    printf("ENTER THE ELEMENTS:");
    for(int i=0;i<n;i++){
    scanf("%d",&a[i]);
    }int low=0,high=n-1;
    printf("ENTER THE ELEMENT TO BE SEARCHED:");
    scanf("%d",&key);
    int flag=binarysearch(a,low,high,key);
    if(flag==-1)
    printf("Search Unsuccessful");
    else 
    printf("Search Successful, Element found at position :%d",flag);
}
int binarysearch(int *a,int low,int high,int key){
    if(low==high)
    {
        if(a[low]==key)
        return low;
        else
        return -1;

    }
    else 
    {
        int mid=low+(high-low)/2;
        if(key==a[mid])
        return mid;
        else if(key>a[mid])
        return binarysearch(a,mid+1,high,key);
        else
        return binarysearch(a,low,mid-1,key);
    }
}

Code Explanation of Binary Search Function.

int binarysearch(int *a, int low, int high, int key)

This function performs a recursive binary search. Let’s break it down

Base Case (Single Element Left):

if (low == high) {
    if (a[low] == key)
        return low;
    else
        return -1;
}

If low equals high, only one element is left to check.

If a[low] (or a[high], as they’re the same) equals key, it returns the index low.

Otherwise, it returns -1 (indicating that key is not found).

Recursive Case (Divide and Conquer):

int mid = low + (high - low) / 2;

mid is calculated to avoid overflow issues by using low + (high - low) / 2 instead of (low + high) / 2.

if (key == a[mid])
    return mid;
else if (key > a[mid])
    return binarysearch(a, mid + 1, high, key);
else
    return binarysearch(a, low, mid - 1, key);

If a[mid] == key, it returns mid, as the key has been found.

If key > a[mid], it recursively searches in the right half by calling binarysearch(a, mid + 1, high, key).

If key < a[mid], it recursively searches in the left half by calling binarysearch(a, low, mid - 1, key).

Output

ENTER THE NUMBER OF ELEMENTS:5
ENTER THE ELEMENTS:1
2
3
4
5
ENTER THE ELEMENT TO BE SEARCHED:3
Search Successful, Element found at position :2

Summary

The main function takes user inputs for an array and a key to search for.The binarysearch function is a recursive implementation that splits the array in half, comparing the middle element to the key.It uses divide and conquer to narrow down the search range by half each time, making it efficient with O(log⁡n) time complexity.

Learn Quick Sort using Divide and Conquer in C along with Pseudo Code Algorithm.

Learn Merge Sort Using Divide and Conquer in C, along with Pseudo Code and Algorithm.