The method of binary search is an algorithm for searching that works on a sorted array by cutting the search time in half over and over again. To reduce the time complexity to O(1), binary search takes advantage of the fact that the array is sorted (Log n). In this post on binary search algorithm, we have discussed the following pointers:
1. What is a binary search algorithm with an example
2. Two standard techniques to implement the binary search algorithm
3. Binary search in c without function
What is exactly a binary search algorithm?
This blog focuses on the binary search algorithm. You must search to find a specific item in a long list. The operation was successful if it checked to see if the element you gave existed in the list and then gave you the element’s index. If there are no good results from a search, it is said to be fruitless.
The linear and binary searches in C are the most common ways to look for something. The subject at hand is the binary search algorithm.
If your information is already in lists, a binary search is the best way to look for it. We must first ensure the list is sorted before using the binary search method to find a specific item in an index.
The fundamental operations of the binary search algorithm are as follows:
- Sort the array in ascending order.
- Put the array’s initial item at the low index and its last at the high index.
- Take the mean of the low and high indices and use that as the intermediate index.
- You should return the middle index if the central index of an element is the one you’re after.
- Set the high index to the middle index minus one if the targeted element is less than the element at the central index.
This means that the low index should be set to the middle index plus one if the target element is greater than the element at the central index.
Example of Binary search Algorithm in C
#include <stdio.h>
int main()
{
int c, first, last, middle, n, search, array[100];
printf(“Enter number of elements\n“);
scanf(“%d”, &n);
printf(“Enter %d integers\n“, n);
for (c = 0; c < n; c++)
scanf(“%d”, &array[c]);
printf(“Enter value to find\n“);
scanf(“%d”, &search);
first = 0;
last = n – 1;
middle = (first+last)/2;
while (first <= last) {
if (array[middle] < search)
first = middle + 1;
else if (array[middle] == search) {
printf(“%d found at location %d.\n“, search, middle+1);
break;
}
else
last = middle – 1;
middle = (first + last)/2;
}
if (first > last)
printf(“Not found! %d isn’t present in the list.\n“, search);
return 0;
}
Output:
Enter the number of elements:
5
Enter 5 integers
24
32
-2
0
49
Enter the value to find
49
49 found at location 5.
There are two standard techniques to implement the binary search algorithm
- The Iterative Method
- The Recursive Method
Program To Implement Binary Search Using Iterative Call
#include <stdio.h>
int iterativeBinarySearch(int array[], int start_index, int end_index, int element){
while (start_index <= end_index){
int middle = start_index + (end_index- start_index )/2;
if (array[middle] == element)
return middle;
if (array[middle] < element)
start_index = middle + 1;
else
end_index = middle – 1;
}
return -1;
}
int main(void){
int array[] = {1, 4, 7, 9, 16, 56, 70};
int n = 7;
int element = 16;
int found_index = iterativeBinarySearch(array, 0, n-1, element);
if(found_index == -1 ) {
printf(“Element not found in the array “);
}
else {
printf(“Element found at index : %d”,found_index);
}
return 0;
}
Output
An element found at index: 4
Also Read : What is Linear Search in C: A Comprehensive Guide
Program To Implement Binary Search Using Recursive Call
#include <stdio.h>
int recursiveBinarySearch(int array[], int start_index, int end_index, int element){
if (end_index >= start_index){
int middle = start_index + (end_index – start_index )/2;
if (array[middle] == element)
return middle;
if (array[middle] > element)
return recursiveBinarySearch(array, start_index, middle-1, element);
return recursiveBinarySearch(array, middle+1, end_index, element);
}
return -1;
}
int main(void){
int array[] = {1, 4, 7, 9, 16, 56, 70};
int n = 7;
int element = 9;
int found_index = recursiveBinarySearch(array, 0, n-1, element);
if(found_index == -1 ) {
printf(“Element not found in the array “);
}
else {
printf(“Element found at index : %d”,found_index);
}
return 0;
}
Output
An element found at index: 3
Binary search in C without function
Here is a binary search example written in C that doesn’t need any functions:
#include <stdio.h>
int main() {
int arr[] = {2, 5, 7, 9, 12, 15, 17, 20}; // sorted array
int n = sizeof(arr) / sizeof(arr[0]); // number of elements in the array
int target = 15; // element to be searched
int low = 0; // lowest index of the search range
int high = n – 1; // highest index of the search range
int mid; // middle index
while (low <= high) {
mid = (low + high) / 2; // calculate the middle index
if (arr[mid] == target) { // target found
printf(“Element found at index %d.\n”, mid);
break;
}
else if (arr[mid] < target) { // target is in the upper half
low = mid + 1;
}
else { // target is in the lower half
high = mid – 1;
}
}
if (low > high) { // target not found
printf(“Element not found.\n”);
}
return 0;
}
Implementation:
Here, we have an ascending-order-sorted array, denoted arr. We need to use binary search to locate a specific element in an array.
Low (starting at 0) to high (the beginning value) is where we begin our indexing journey (which is initially n-1, where n is the number of elements in the array).
Following this, we take the mean of the low and high indices to arrive at the middle index, mid. We compare the element at the midpoint with the target. If they are equal, the index at which the target was located is printed, and the loop exits. If the value at mid is smaller than the desired value, we narrow our search to the upper half of the array by setting low to mid+1. If the value at mid is larger than the desired value, we restrict our search to the lower half of the array by setting high to mid-1.
This method is carried out until the target is found or the search area is no longer needed (i.e., low becomes greater than high). An error message will be displayed if the specified element cannot be located.
Keep in mind that this implementation depends on the array being key-sorted. The binary search algorithm will only succeed if the array is sorted.
Conclusion
To sum up, binary search is a powerful way to find information in ordered lists. The time it takes is O (log n), where n is the number of items in the array. The algorithm cuts the search area in half until the desired element is found or the search area is complete. This makes the algorithm much faster than a linear search because it cuts down on the number of things that must be looked for at each stage.
C’s implementation of binary search is as simple as writing a loop to continually split the search range in half and update the low and high indices.
Other algorithms use a recursive function that calls itself on the sub arrays made when the search range is cut in half. The array must be in the correct order for the binary search to work. The results will be accurate if the varieties are in the correct order.
For more interactive topics, visit educationnest.com right away!
