Binary Search Program in C

Last Updated on November 1, 2023 by Ankit Kochar

A C program for binary search is a widely employed search algorithm in the realm of computer programming. It stands out as an efficient method for locating a desired value within a sorted array or list by iteratively partitioning the search range in half. In a C program implementing binary search, the algorithm commences by comparing the target value with the middle element of the array. If the middle element aligns with the target value, the search is successfully concluded. Should they differ, the search interval undergoes further halving, directing the quest into the appropriate subarray. This process is iterated until either the sought-after value is located or the subarray in question becomes devoid of elements. Notably, binary search boasts a time complexity of O(log n), rendering it markedly swifter than linear search when applied to substantial arrays or lists.

What is a Binary Search in C?

Binary Search in the C programming language represents a search strategy applied to sorted arrays. It involves the iterative division of the search range in half. By capitalizing on the prior knowledge that the array is sorted, binary search efficiently minimizes the time complexity to O(LogN).
With this method, the middle of an array is always searched for the element.

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

• Recursive Method
• Iterative Method

Example for Binary Search in C

Item to be searched=20

Input:

beg=0, end=4, mid=2

beg=3, end=4, mid=3

An element found at index 3, Hence 3 will get returned.

Explanation For Binary Search Program In C

The binary search program in C can be 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 elements. The key is then compared to the midpoint value. If the 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.

Algorithm For Binary Search In C

Here is the algorithm for binary search in C:

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.

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 Code in C

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

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 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 time 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).

Advantages of Binary Search in C

Here are the advantages of binary search in C:

• Fast and efficient with time complexity of O(log n)
• Simple and easy to implement
• Space-efficient, without requiring additional memory allocation or data structures
• Accurate results for exact matches and nearest element searches
• Versatile and applicable in various applications.

Disadvantages of Binary Search in C

Here are some disadvantages of binary search in C:

• It can only be used on sorted arrays
• Requires extra space if a recursive implementation.
• Not suitable for dynamic arrays or lists
• Binary search can be slower than linear search for very small arrays or datasets

Conclusion
In this exploration of the Binary Search Program in C, we’ve delved into a fundamental and highly efficient searching technique that is particularly suited for sorted arrays. Binary search leverages the structure of sorted data to repeatedly divide the search interval in half, which results in a time complexity of O(LogN). This efficiency makes it a preferred choice for searching in large datasets where linear search would be far less practical.
By understanding the principles of binary search and implementing it in the C programming language, developers can create optimized and effective search solutions. Whether used in academic exercises or real-world applications, binary search remains a fundamental and valuable tool in a programmer’s repertoire.

Frequently Asked Questions(FAQs) related to Binary Search Program in C

Here are some of the FAQs related to Binary search program in C:

1. When should I use Binary Search in C?
Binary search is best employed when you have a sorted dataset, and you need to locate a specific value efficiently. It is particularly useful for large datasets where a linear search would be slow.

2. What is the time complexity of Binary Search in C?
The time complexity of binary search is O(LogN), which means that the number of operations required grows logarithmically with the size of the dataset. This makes it highly efficient for large datasets.

3. Is Binary Search always faster than Linear Search?
Binary search is faster than linear search only when the data is sorted. If the data is not sorted, linear search is often more appropriate.

4. How can I implement Binary Search in C?
Implementing binary search in C involves defining the search range and repeatedly dividing it in half. It typically uses a loop or recursive function. Be sure to take into account the sorted nature of the data and handle edge cases.

5. Are there any limitations to Binary Search in C?
Binary search requires the data to be sorted. If the data is not sorted or if you need to maintain an unsorted dataset, other search algorithms like linear search or hash-based searches may be more appropriate.

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