Binary Search

Binary search is a searching algorithm, it applies to finding an element in a sorted array. In the binary search, we will divide the half by comparing the element to be searched with the middle element of the array. If the array is not sorted you must use sorting techniques like merge sort or quick sort, etc, and perform a binary search operation. As we deal with the sorted arrays it is a best case that performs a minimum number of steps.

The time complexity of the binary search algorithm is O(log n).

How does Binary Search Work?

Binary search applies only to the sorted arrays. The search element starts by comparing with the middle element in the array.

• If the value matches then it returns its position.
• In case, the search element is less than a middle element of the array (considering the array is in ascending order) discard the second half of the array and the search continues by dividing the first half of the array.
• Similarly, if the search element is greater than a middle element of the array(considering the array is in ascending order)discard the first half of the array and the search continues by dividing the second half of the array.

Binary Search can be performed in two ways:

1. Recursion Method
2. Iterative Method

Binary Search Recursive Method

Binary Search in C using Recursion

#include <stdio.h>
int binarySearch(int arr[], int l, int r, int search) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 
        if (arr[mid] == search) 
            return mid; 
        if (arr[mid] > search) 
            return binarySearch(arr, l, mid - 1, search); 
        return binarySearch(arr, mid + 1, r, search); 
    } 
    return -1; 
} 
int main() 
{ 
    int arr[] = { 7, 9, 4, 11, 4 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int search = 11; 
    int position = binarySearch(arr, 0, n - 1, search); 
    (position == -1) ? printf("The element is not present in array") 
                   : printf("The element is present at index %d", 
                            position); 
    return 0; 
}

Output

The element is present at index 3

Explanation:

In the above Binary search, we use the recursion method,binarySearch() function repeatedly calls itself until the base condition reached some specified condition which is discussed below:

• If the arr[mid] is greater than the search element, we call the binarySearch(arr, l, mid – 1, search) with the start as mid+1.
• If the arr[mid] is less than the search element, we call the binarySearch(arr, l, mid + 1, search) with the end as mid-1.
• There are two exit conditions for this recursion:
  • If the element is found then return mid.
  • If the search element is not found, it will return -1, i.e start is greater than the end.

Binary Search Iterative Method

Binary Search in C using Iterative

#include <stdio.h>
int binarySearch(int arr[], int n, int search)
{
    int low = 0, high = n - 1;
 
    while (low <= high)
    {
        int mid = (low + high)/2;    
        if (search == arr[mid]) {
            return mid;
        }
        else if (search < arr[mid]) {
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    }
    return -1;
}
 
int main()
{
    int arr[] = {  7, 9, 4, 11, 4};
    int search= 11;
 
    int n = sizeof(arr)/sizeof(arr[0]);
    int index = binarySearch(arr, n, search);
 
    if (index != -1) {
        printf("Element found at index %d", index);
    }
    else {
        printf("Element not found in the array");
    }
 
    return 0;
}

Output

Element found at index 3

Explanation:

In the above Linear Search, we use the iterative method, which is looping over the same block of code multiple times until some specified conditions discussed below-

• If the search element is equal to arr[mid], then it returns mid.
• If the search element is less than arr[mid], then high = mid – 1 until the element is found.
• If the search element is greater than arr[mid], then low = mid + 1 until the element is found.

The exit condition for this iterative is:

• if the element is not found, then it returns -1,i.e it is low is greater than high.

Follow us on Facebook, YouTube, Instagram, and Twitter for more exciting content and the latest updates.