How to implement the binary search algorithm in the C language?

2 years ago
William Carter
2 minutes

Binary search, also known as half-interval search, requires the array being searched to be sorted.

The binary search algorithm can be implemented by following these steps:

  1. Create a function that takes a sorted array and the target element to be searched as parameters.
  2. Initialize two pointers, one pointing to the beginning of the array, and one pointing to the end of the array.
  3. Use a loop to determine if the starting position is less than or equal to the ending position.
  4. Within the loop, the index of the middle position is calculated as the sum of the starting and ending positions divided by two.
  5. If the middle element is equal to the target element, return the index of the middle position.
  6. If the element in the middle position is greater than the target element, move the end position pointer to the previous position of the middle.
  7. If the element in the middle position is smaller than the target element, move the starting position pointer to the position after the middle position.
  8. If the target element is not found at the end of the loop, return -1 to indicate that the search has failed.

Here is an example code:

#include <stdio.h>

int binarySearch(int arr[], int target, int start, int end) {
    while (start <= end) {
        int mid = start + (end - start) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    
    return -1;
}

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

The code searches for the target element 12 in a sorted array and outputs its index. If the target element is found in the array, the corresponding index is output; otherwise, “Element not found” is output.

bannerAds