Binary Search in Data Structures using C
The binary search algorithm can iteratively search a sorted array by halving the search interval. By using the fact that the array is sorted, binary search tries to reduce the amount of time required.
When to use a data structure's binary search feature:
Binary Search algorithm application:
- Sorting of the data structure is required.
- Accessing any data structure element always takes the same amount of time.
The kind of search that functions best with sorted lists is a binary search. Therefore, we must ensure the list is sorted before utilizing the binary search strategy to find an element.
In binary search, the item is compared to the middle element of the list after the list has been divided into two halves. This is known as the divide and conquer technique.
Note: Binary search can be applied to sorted array elements. If the list's elements still need to be arranged in a sorted manner, we must first sort them.
Binary Search Algorithm:
- The binary search method uses the middle index "mid" to divide the search space into two equal parts.
- Using the binary search algorithm to get the middle index "mid."
- Compare the key to the search space's middle component.
- The process is finished if the key is located at the center element.
- Pick which half will be utilized as the next search space if the key cannot be discovered at the middle element.
- If the key is smaller than the center element, the left side is used for the subsequent search.
- If the key is larger than the center element, the right side is used for the subsequent search.
- Up till the key is located, this process is continued.
The first array element's index, the last array element's index, is indicated by "higher," and the value to be searched for is indicated by "val."
Step 1:Set start = lower, end =higher, and pos is =-1
Step 2: Repeat till steps 3 and 4 while start=end
step 3: Set mid = (start + end)/2
step 4: If a[mid] = val
set pos = mid
print pos,
go to step 6
else, if a[mid] > val
set end = mid - 1,
else
Set start =mid+1
(end of if)
(end of the loop)
step 5:is if pos = -1.
to output "not found."
Step 6: exit
How Can Binary Search Be Used?
The Binary Search Algorithm can put into practice using one of the following two techniques:
- Iterative Binary search algorithm.
- Recursive Binary search algorithm.
Iterative search algorithm
In this iterative binary search technique, we compare the key and split the search space into two halves.
- The sorting method known as a binary search can be used to look up an element in an array that has been sorted.
- Since binary search only works on sorted arrays, an array must first be sorted before using it.
- The binary search method outperforms the liner search method as the number of iterations decreases.
The assumption that a key exists justifies the binary search. This key stores the value to be searched. The array's initial and last elements and its highest and lowest values. The array's initial and last values and its first and last element.
Example:
#include<stdio.h>
int binarySearch(int a[], int val, int l, int h) {
// Repeat until the pointers low and high meet each other
while (l <= h) {
int mid = l + (h - l) / 2;
if (a[mid] == val)
return mid;
if (a[mid] < val)
l = mid + 1;
else
h = mid - 1;
}
return -1;
}
int main(void) {
int a[] = {1, 2, 3, 4, 5};
int n = sizeof(a) / sizeof(a[0]);
int val = 4;
int res = binarySearch(a, val, 0, n - 1);
if (res == -1)
printf(" Search Not found");
else
printf(" Search val is found at index %d", res);
return 0;
}
Output:
![Binary Search in Data Structures using C](https://static.tutorialandexample.com/c/binary-search-in-data-structures-using-c1.png)
In the program above, we declare val, l, h, mid, n, and an [size].
- The array is iterated over using the variable i.
- The initial array index is held in the variable l for low.
- The last array index is stored in the variable h for high.
- The middle or mid value is obtained when high and low are added together and divided by two.
- The array's size in elements is n.
- The element to look for is val.
- A is the size array element.
Recursive Binary Search
Make a recursive function, and compare the key's midpoint with the search space's midpoint. And depending on the outcome, either invoke the recursive procedure for the following search space or return the index where the key was discovered.
Example:
#include<stdio.h>
int binaryRecu(int arr[], int l, int h, int key)
{
if (h >= l) {
int mid = l + (h - l) / 2;
if (arr[mid] == key)
return mid;
if(arr[mid] > key)
return binaryRecu(arr, l, mid - 1, key);
return binaryRecu(arr, mid + 1, h, key);
}
return -1;
}
int main(void)
{
int arr[] = { 1, 3, 11, 56, 90 };
int i, key;
/*for(i=0;i<5;i++){
printf(" %d",arr[i]);
}
printf(" n");*/
int n = sizeof(arr) / sizeof(arr[0]);
printf("enter the key element");
scanf("%d", &key);
int res = binaryRecu(arr, 0, n - 1, key);
if(res==-1)
printf("The element is not found");
else
printf("Search successful key found at index %d",res);
return 0;
}
Output:
![Binary Search in Data Structures using C](https://static.tutorialandexample.com/c/binary-search-in-data-structures-using-c2.png)
The function BinaryRecu is used in the program above to search for the element in the array. The element is searched by calling the function repeatedly.
- We take the user's input and store it in the key. The array has been declared and initialized.
- We call the BinaryRecu function and pass the array, lower and higher indexes, and the number to be searched along with the result parameter.
- The function carries out a recursive binary search. If the item cannot be located, it returns -1. Ternary operations are employed in the primary function.
- Nothing was detected if the result was 1; otherwise, something was found.
Time Complexity:
Best Case : O(1)
Average Case: O(log N)
Worst Case: O(log N)
Advantages of Binary Search:
Compared to other search algorithms, binary search is a potent and effective method with many benefits, especially when dealing with sorted data.
The following are a few noteworthy advantages of binary search:
Practical: The binary search algorithm's time complexity is O(log n). Each iteration cuts the search space in half, significantly lowering the number of comparisons necessary to locate the desired piece.
Versatility: A range of values can be located using binary search.It can also be modified to determine the value closest to a specified target or identify where to insert a new element in a sorted array.
Simplicity: The fundamental idea behind binary search is straightforward. It entails continually halving the search area until the target element is discovered or is determined to be nonexistent.
Memory Efficiency: Binary search only needs the sorted array and no further data structures. This makes it memory-efficient and appropriate for situations with little available memory.
Accurate result: Binary search, when used on data that has been sorted, ensures accurate results. Binary search will locate the target element in the array if it is there. Binary search will appropriately identify the element's absence if it's absent.
Disadvantages of Binary Search:
- Array Structures: Binary search is most frequently used with arrays or lists since it is adequate to access elements by index in these structures. The effectiveness of binary search may suffer if the data is kept in a different data structure, such as a linked list because sequential traversal is required.
- The complexity of insertion and deletion: Adding or removing members from a sorted array might be difficult and expensive while keeping the order. The array must be changed appropriately for these operations, which may require shifting many members.
- Sorted data Required: Arranged data that has been sorted must be put in ascending or descending order to use binary search. Binary search, however, can be very effective if the data has already been sorted or if it can be sorted once and searched several times.
- Limited Usage: Binary search is only helpful in looking for a single element in a sorted collection. It is not appropriate for situations requiring numerous matches or range searches.
- Lack of Real-Time Updates: Binary search may not be the best option if the sorted data set is dynamic and often updated or modified.
- Memory overhead: A contiguous memory block is needed to store the sorted array for binary search.
Applications of Binary Search:
- Database search: Database systems typically utilize binary search to look for specific records based on a critical value.
- It was locating Elements in Sorted Arrays: Binary search effectively finds elements in sorted arrays. It is helpful when you need to find a specific element's position or index in an array or check to see if it exists.
- Autocorrection and Spell Checking: Binary search is frequently used in autocorrection systems or spell-checking algorithms to determine whether a word is contained in a sorted dictionary or to suggest substitute words based on similar patterns.
- Lower and Upper Bound Search: In a sorted array, binary search can determine a given value's lower and upper bounds. Binary search techniques can be modified to identify items in rotated or shifted arrays, where the elements are ordered but are moved cyclically.
- Game Playing and Decision Making: Binary search can be used in game-playing algorithms to make decisions or look for particular game situations effectively.