What Is Binary Search in Data Structure in C?

Binary search is a fundamental algorithm in computer science and a key concept in the field of data structures. It is used to efficiently search for a specific element in a sorted array or list. In this article, we will explore the concept of binary search in the context of data structures, specifically focusing on its implementation in the C programming language.

Understanding Binary Search

Binary search follows a divide-and-conquer approach to locate an element within a sorted array. It repeatedly divides the search space in half by comparing the Target element with the middle element of the array. Based on this comparison, it either continues searching in the left or right subarray.

The algorithm works as follows:

1. Step 1: Start with an array sorted in ascending order.
2. Step 2: Set two pointers, low and high, to the first and last indices of the array respectively.
3. Step 3: Calculate mid, which represents the index of the middle element.
4. Step 4: Compare the Target element with the middle element:
   • If they are equal, return the index of the middle element.
   • If the Target is less than the middle element, update high to mid – 1 and go back to Step 3.
   • If the Target is greater than the middle element, update low to mid + 1 and go back to Step 3.
5. Step 5: Repeat Steps 3-4 until low becomes greater than high. This indicates that the Target element is not present in the array.

Implementing Binary Search in C

Let’s now look at an example implementation of binary search in C:

#include <stdio.h>

int binarySearch(int arr[], int low, int high, int Target) {
  while (low <= high) {
    int mid = low + (high - low) / 2;
    
    if (arr[mid] == Target)
      return mid;
    
    if (arr[mid] < Target)
      low = mid + 1;
    
    else
      high = mid - 1;
  }
  
  return -1; // Target element not found
}

int main() {
  int arr[] = {2, 4, 6, 8, 10, 12};
  int n = sizeof(arr) / sizeof(arr[0]);
  
  int Target = 8;
  
  int result = binarySearch(arr, 0, n - 1, Target);
  
  if (result == -1)
    printf("Element not found\n");
  
  else
    printf("Element found at index %d\n", result);
    
   return 0;
}

In this example, we have an array arr containing sorted integers. We want to search for the element target and find its index using binary search.

The binarySearch function takes four parameters: the array arr, the lower index low, the higher index high, and the Target value target. It returns the index of the Target element if found; otherwise, it returns -1.

The main function initializes the array and calls the binarySearch function. It then prints the appropriate message based on the search result.

Conclusion

Binary search is a powerful algorithm that allows for efficient searching in sorted arrays. By dividing the search space in half with each iteration, it significantly reduces the number of elements to be examined. This makes it a preferred choice when dealing with large datasets.

In this article, we explored binary search in the context of data structures and implemented it in C. Remember to always use binary search on sorted arrays and lists for accurate results.