Binary Search Program in C

We’ll talk about the binary search program in C programming language in this article. Finding a certain element in the list is the process of searching. The method is deemed successful and returns the element’s location if the element is present in the list. If not, the search is deemed fruitless.

The 2 most used search methods are linear search & binary search. We’ll talk about the Binary Search Algorithm here.

The search strategy that performs well on sorted lists is binary search. Thus, we must ensure that now the list is sorted before using the binary search strategy to find an element in it.

In binary search, the item is compared to the list center element after being split into two halves, which is known as the divide and conquer approach. The location of the middle element is returned if a match is discovered. Otherwise, we examine any half, depending on how the game turns out.

What is a Binary Search Program In C?

Binary Search in C programming language is a searching technique used in a sorted array by repeatedly dividing the search interval in half. Utilizing the knowledge that the array is sorted, binary search focuses on decreasing the time complexity to O(LogN).
With this method, an arrays middle is always searched for the element.

For creating binary search program in C, there are two methods-

  • Recursive Method
  • Iterative Method

Logic For Binary Search Program In C

The binary search is justified by the assumption that there is a key. The value to be searched is stored in this key. The sum of the two values—the highest and lowest—is divided by two. The array’s highest and lowest values, as well as its first and last element. The key is then compared to the midpoint value. If mid is the same as the key, we receive the output immediately. The operation is repeated on the condensed array if the key is greater than mid, in which case mid+1 becomes the lowest value. Otherwise, mid-1 becomes the greatest value and the process is repeated on the reduced array if the key value is smaller than mid. A not found notice is shown if it can’t be found anywhere.

Explanation with Example

Item to be searched=20
Input:

0 1 2 3 4
10 11 16 20 23

beg=0, end=4, mid=2

0 1 2 3 4
10 11 16 20 23

beg=3, end=4, mid=3

0 1 2 3 4
10 11 16 20 23

Element found at index 3, Hence 3 will get returned.

Algorithm For Binary Search Program In C Language

The general steps for both methods (iterative and recursive) are discussed below:

  1. Read the search element from the user.
  2. Find the middle element in the sorted array.
  3. Compare the search element with the middle element in the sorted array.
  4. If both are matched, then display "Given element is found!!!" and terminate the function.
  5. If both are not matched, then check whether the search element is smaller or larger than the middle element.
  6. If the search element is smaller than the middle element, repeat steps 2, 3, 4 and 5 for the left subarray of the middle element.
  7. If the search element is larger than the middle element, repeat steps 2, 3, 4 and 5 for the right subarray of the middle element.
  8. Repeat the same process until we find the search element in the array or until the subarray contains only one element.
  9. If that element also doesn’t match with the search element, then display "Element is not found in the array!!!" and terminate the function.

Pseudo Code Of Both the Logics (Recursive and Iterative) For Binary Search Program In C

Here, we will discuss the pseudo code for both of the approaches i.e. recursive as well as iterative for binary search program in C programming language.

Iteration Method for Binary Search in C

do until the pointers low and high meet each other.

    mid = (low + high)/2
    if (x == arr[mid])
        return mid
    else if (x > arr[mid]) // x is on the right side
        low = mid + 1
    else                       // x is on the left side
        high = mid - 1

Recursive Method for Binary Search in C

binarySearch(arr, x, low, high)

    if high >= low
        mid = (low + high) / 2 
        if x == arr[mid]
            return mid
        else if x > arr[mid]        // x is on the right side
            return binarySearch(arr, x, mid + 1, high)
        else                               // x is on the right side
            return binarySearch(arr, x, low, mid - 1)
    return -1

Binary Search Code Implementation in C (Recursive Method)

#include <stdio.h>  
int binarySearch(int a[], int beg, int end, int val)    
{    
    int mid;    
    if(end >= beg)     
    {        mid = (beg + end)/2;    
        if(a[mid] == val)    
        {                 
            return mid+1;    
        }    

        else if(a[mid] < val)     
        {  
            return binarySearch(a, mid+1, end, val);    
        }    

        else     
        {  
            return binarySearch(a, beg, mid-1, val);    
        }          
    }    
    return -1;     
}   
int main() {  
  int a[] = {11, 14, 25, 30, 40, 41, 52, 57, 70};  
  int val = 40;
  int n = sizeof(a) / sizeof(a[0]);  
  int res = binarySearch(a, 0, n-1, val);  
  printf("The elements of the array are - ");  
  for (int i = 0; i < n; i++)  
	printf("%d ", a[i]);   
  printf("\nElement to be searched is - %d", val);  
  if (res == -1)  
  printf("\nElement is not present in the array");  
  else  
  printf("\nElement is present at %d position of array", res);  
  return 0;  
}  

Output:
The elements of the array are - 11 14 25 30 40 41 52 57 70 
Element to be searched is - 40
Element is present at 5 position of array

Binary Search Code Implementation in C(Iterative Method)

#include <stdio.h>

int binarySearch(int array[], int x, int low, int high) {
  while (low <= high) {
    int mid = low + (high - low) / 2;

    if (array[mid] == x)
      return mid;

    if (array[mid] < x)
      low = mid + 1;

    else
      high = mid - 1;
  }

  return -1;
}

int main(void) {
  int array[] = {3, 4, 5, 6, 7, 8, 9};
  int n = sizeof(array) / sizeof(array[0]);
  int x = 4;
  int result = binarySearch(array, x, 0, n - 1);
  if (result == -1)
    printf("Not found");
  else
    printf("Element is found at index %d", result);
  return 0;
}

Output:
Element is found at index 1

Time Complexity of Binary Search

Table showing the time complexity of binary search program in C programming language.

Scenario Time Complexity
Best Case O(1)
Average Case O(logn)
Worst Case O(logn)

Best Case Complexity – In a binary search, the best case scenario is when the searchable element is discovered in the first comparison, or when the first middle element is in fact the searchable element. Binary search has a best-case temporal complexity of O(1).

Average Case Complexity – For a binary search, the average case time complexity is O(logn).

Worst Case Complexity – The worst case scenario for binary search is when we have to continuously narrow the search space until there is just one element. Binary search has a worst-case temporal complexity of O(logn).

Space Complexity For Binary Search Program In C
The Space complexity for coding binary search program in C is O(1).

Tips for Binary Search in C:

On sorted array elements, binary search can be applied. We must first sort the list elements if they are not already organized in a sorted fashion.

Conclusion
This blog has discussed the flow and implementation of both methods (iterative and recursive) for binary search program in c. We hope this article helps you to enhance your knowledge and gives you a grasp to solve more similar problems. Also, you can visit PrepBytes for practicing more similar questions.

Other C Programs

C Program to Add Two Numbers
C Program to Calculate Percentage of 5 Subjects
C Program to Convert Binary Number to Decimal Number
C Program to Convert Celsius to Fahrenheit
C Program to Convert Infix to Postfix
C Program to Find Area of Circle
C Program to Find Roots of Quadratic Equation
C program to Reverse a Linked List
C program to reverse a number
Ascending Order Program in C
Menu Driven Program For All Operations On Doubly Linked List in C
C Program for Armstrong Number
C Program For Merge Sort For Linked Lists
C program for performing Bubble sort on Linked List
Hello World Program in C
Perfect Number Program in C
Leap Year Program in C
Odd Even Program in C
Selection Sort Program in C

Leave a Reply

Your email address will not be published. Required fields are marked *