# C PROGRAMS
Array Programs
➤ Find Length of Array
➤ How to Print an Array
➤ Sum of Array Elements
➤ Reverse an Array in C
➤ Copy an Array in C
➤ Merge Two Arrays in C
➤ Merge Two Sorted Arrays
➤ Count Repeated Elements
➤ Find Duplicate Elements
➤ Linear Search in C
➤ Binary Search in C
➤ Insert Element in Array
➤ Delete Element in Array
➤ Display odd-even in Array
➤ Sum & Count of Odd-Even
➤ Count +ve, -ve, & 0
➤ Sum of +ve, -ve Numbers
➤ Avg & Numbers > Avg
➤ Smallest & Largest Element
➤ 1st 2nd Max-Min
➤ Sort Array in C
➤ Search element in Array
➤ Search index of Nth times occurred element
➤ Matrix Programs
Binary search program in C Programming Language. Binary search is an efficient algorithm for finding an item from a sorted list or array of items. Sometimes it is also known as half-interval search, logarithmic search, or binary chop.
Condition to use binary search:- The array must be sorted.
The binary search algorithm cannot be applied to unsorted arrays. This algorithm can be used when the array has terms occurring in order of increasing size (for instance: if the terms are numbers, they are listed from smallest to largest; if they are words, they are listed in lexicographic, or alphabetic, order). If the array or list is not sorted then before applying the binary search algorithm, first sort the array or list.
The binary search algorithm can be written in two ways. These are,
a) Recursive approach
b) Iterative approach
Binary Search in C using Recursion
In the recursive approach, the recursion technique is used. It is an example of the divide and conquers technique where bigger problems are divided into smaller problems. Like all divide and conquer algorithms binary search first divide the large array into smaller sub-arrays and then solve it recursively. It us see it in detail.
Binary Search Algorithm in C using Recursive Approach
a) Take an array, initial index, size, and search key.
b) Find the middle term.
c) if middle term == search key then return index.
d) if middle term > search key then apply recursive call on the first half of the array.
e) else apply recursive call on the second half of the array.
f) Repeat the process until the search key not matched.
g) If not matched then return -1.
It can be written as,
int binarySearch(arr, low, high, key)
{
if (high >= low) {
int mid = low + (high - low) / 2;
if (arr[mid] == key) return mid;
if (arr[mid] > key)
return binarySearch(arr, low, mid - 1, key);
return binarySearch(arr, mid + 1, high, key);
}
return -1;
}
The time complexity of this algorithm = O(log n)
How Recursive approach works?
In binary search using the recursive approach, we split the array from the middle into two subarrays of the same size or where one of these smaller lists has one fewer term than the other. Let us understand it through an example.
Array = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
Example
Assume the search term = 40. Then the steps in binary search,
- Find the middle term of the array. If the size of array is odd then middle-index = (size – 1)/2 else middle-index = size/2. In our example, middle index = 10/2 = 5, and middle term is array[3] = 60
- Compare middle term and search term. If the middle term > search term then it may exist in the first portion of the array else in the second portion of the array. Since 60 > 40 therefore search term may exist only in the first portion of the array.
- Split the array into two parts from the middle index. The subarr1 = {10, 20, 30, 40, 50} and subarr2 = {60, 70, 80, 90, 100}.
- Since the array is sorted and 60 > 40, therefore search terms may exist only in the first sub-array. Forgot about the second sub-array, no use of it, only the first sub-array is required for the next step. Now, assume the original array = {10, 20, 30, 40, 50}, and search term = 40.
- Repeat the same process with first sub array. Find the middle term. The middle index = (5-1)/2 = 2, middle term is array[2] = 30
- Compare middle term with the search term, 30 < 40 therefore it may exist only in the second portion.
- Split array into two subarrays from the middle index. The new sub arrays are:- subarr1 = {10, 20} and subarr2 = {30, 40, 50}. Only subarr2 will be considered for the next steps, no use of subarr1. Now, assume array = {30, 40, 50} and search term = 40. Repeat the process.
- Find middle term. The middle index = (3-1)/2 = 1 and the middle term is array[1] = 40.
- Compare middle term and search term. Currently, both are equal and the match is found.
C Program to implement Binary Search using Recursion
Now let us see the implementation of the binary search algorithm in the C programming language. Here the function binarySearch() finds the index of the search key, if the match is found then it returns the index of the search key else it returns -1.
#include <stdio.h>
// recursive function for binary search
/* if match found then return index of search key
else return -1 */
int binarySearch(int arr[], int low, int high, int key) {
if (high >= low) {
// find middle index
int mid = low + (high - low) / 2;
// find middle term and compare
if (arr[mid] == key) return mid; // key found
// If key is smaller than middle term, then
// it can only be present in left subarray
if (arr[mid] > key)
return binarySearch(arr, low, mid - 1, key);
// Else the key can only be present
// in right subarray
return binarySearch(arr, mid + 1, high, key);
}
// key not found
return -1;
}
// main function
int main()
{
int array[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int key = 0;
// Enter search key
printf("Enter Search Element: ");
scanf("%d", &key);
// find the array size
int size = sizeof(array)/sizeof(array[0]);
// search key
int index = binarySearch(array, 0, size, key);
if(index == -1)
printf("%d Not Found\n", key);
else
printf("%d Found at Index = %d\n", key, index);
return 0;
}
Output:-
Enter Search Element: 40
40 Found at Index = 3
Enter Search Element: 99
99 Not Found
Enter Search Element: 10
10 Found at Index = 0
Binary Search in C using Iterative approach
In this approach, instead of calling the method recursively, we use iteration to traverse the array and find the search key. Both approaches are quite the same, with two differences in implementation.
In the recursive method, there is no loop, and rather than passing the new values to the next iteration of the loop, it passes them to the next recursion. In the iterative method, the iterations can be controlled through the looping conditions, while in the recursive method, the maximum and minimum are used as the boundary condition.
Algorithm
To search for the integer x in the list/array a1, a2 , … ,an , where list/array is in ascending order (a1 < a2 < ··· < an) ,
- begin by comparing x with the middle term am of the list/array, where m = ⌊(n + 1)/2⌋.
- If x > am, the search for x is restricted to the second half of the list, which is am+1, am+2, …, an.
- If x is not greater than am, the search for x is restricted to the first half of the list, which is a1, a2, …, am.
- The search has now been restricted to a list with no more than ⌊n/2⌋ elements.
- Using the same procedure, compare x to the middle term of the restricted list.
- Then restrict the search to the first or second half of the list.
- Repeat this process until a list with one term is obtained.
- Then determine whether this term is x.
The algorithm can be written as,
int binary search (a: array, low, high, x: search-key) {
i := low; // i is left endpoint of search interval
j := high; // j is right endpoint of search interval
while (i < j) {
m := ⌊(i+j)/2⌋
if x > a[m] then i := m+1
else j := m
}
if x=a[i] then location := i
else location := -1
return location
}
C Program
C program for binary search using iterative approach,
#include <stdio.h>
// function for binary search
/* if match found then return index of search key
else return -1 */
int binarySearch(int arr[], int low, int high, int key) {
int i = low; // left index
int j = high; // right index
int mid = 0;
while(i < j) {
// find middle index
mid = (i+j) / 2;
// compare search key and middle term
if(key > arr[mid])
i = mid + 1;
else
j = mid;
}
// when i==j
if(key == arr[i])
return i; // key found
return -1; // key not found
}
// main function
int main()
{
int array[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int key = 40; // search key
// find the size array
int size = sizeof(array)/sizeof(array[0]);
// search key
int index = binarySearch(array, 0, size, key);
if(index == -1)
printf("%d Not Found\n", key);
else
printf("%d Found at Index = %d\n", key, index);
return 0;
}
Output:-
40 Found at Index = 3
C Program to Search a Character from the list of Characters
Program description:- Write a program to search a character from the list of characters using a binary search algorithm.
#include <stdio.h>
// function for binary search
int binarySearch(char arr[], int low, int high, char key) {
int i = low; // left index
int j = high; // right index
int mid = 0;
while(i < j) {
// find middle index
mid = (i+j) / 2;
// compare search key and middle term
if(key > arr[mid])
i = mid + 1;
else
j = mid;
}
// when i==j
if(key == arr[i])
return i; // key found
return -1; // key not found
}
// main function
int main()
{
char array[] = {'K', 'P', 'a', 'g', 'm', 'n', 'o', 'r', 'w'};
char key = '\0';
// Enter search key
printf("Enter Search Element: ");
scanf("%c", &key);
// find the array size
int size = sizeof(array)/sizeof(array[0]);
// search key
int index = binarySearch(array, 0, size, key);
if(index == -1)
printf("%c Not Found\n", key);
else
printf("%c Found at Index = %d\n", key, index);
return 0;
}
Output:-
Enter Search Element: A
A Not Found
Enter Search Element: a
a Found at Index = 2
Binary Search Time Complexity
Best-case time complexity | O(1) | When the search key present at the center (middle term) of the array/list. |
Worst-case time complexity | O(log n) | When the search key is not available or at the extremity of the list. |
In the iterative method, the space complexity would be O(1). While in the recursive method, the space complexity would be O(log n).
For the small arrays linear search algorithm gives better performance compared to the binary array, but for the large arrays if the array is in sorted order then the binary search gives better performance compared to the linear search.
There are specialized data structures designed for fast searching, such as hash tables, that can be searched more efficiently than binary search. However, binary search can be used to solve a wider range of problems, such as finding the next-smallest or next-largest element in the array relative to the target even if it is absent from the array.
If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!