Example 63: Binary Search
Understand how to perform binary search on a sorted array by repeatedly dividing the array and comparing the target element with the middle value. Learn to efficiently search elements in C programs using this divide and conquer method. This lesson guides you through writing a binary search function and interpreting its step-by-step process.
We'll cover the following...
Problem
The binary search method is a fast and efficient searching algorithm. This method requires that the list of elements be in sorted order. It is based on the Divide and Conquer Algorithm as it divides the array into two parts.
Write a function that performs a binary search on an array of 10 integers.
Demonstration
Suppose an array consists of 10 sorted numbers, and 57 is the element to be searched. When applied to this array, the binary search method works as follows:
- 57 is compared with the element present at the centre of the list (i.e., 11). Since 57 is greater than 11, the searching is restricted only to the second half of the array.
- Now, 57 is compared with the centre element of the second half of the array (i.e., 25). Here again, 57 is greater than 25, so the searching now proceeds in the elements present between the 25 and the last element 90.
- This process is repeated till 57 is found, or no further division of the sub-array is possible.
Example
Array = {1, 2, 3, 9, 11, 13, 17, 25, 57, 90}