C Binary Search

Summary: in this tutorial, you will learn how to implement the C binary search algorithm. We will show you how to implement the binary search algorithm using recursion and iteration techniques.

Introduction to the binary search algorithm

Binary search is used to find the position of a key in a sorted array. The following describes the binary search algorithm:

  • We compare the key with value in the middle of array. If the key match found, we return its position, which is the index of the middle element of the array.
  • If the key is less than the value of the middle element of the array, we repeat the above step on the sub-array on the left. If the key is greater than the value of the middle element of the array, we repeat the above step on the sub-array on the right.
  • If the sub-array to be searched has zero item, it means the key cannot be found.

The binary search technique performs searches on each half of the array in each step therefore it is known as half-interval search.

C binary search implementation

Notice that the following code is just a demonstration of implementing the binary search alogrithm in C. If you want to use binary search function, use the C bsearch() built-in function.

We can implement the binary search algorithm in C using recursion and iteration techniques.

C binary search using recursion technique

C binary search using iteration technique

We can write a program to test our binary search functions:
The following is the output of the program:
In this tutorial, we have shown you how to implement binary search in C using recursion and iteration techniques.