Last updated on September 4th, 2023 at 09:41 pm
Here, We discuss about Binary Search, their implementation in C, time and space complexity and its applications.
What is Binary Search?
Binary Search is the most popular searching algorithm. It is efficient and most commonly used to solve problems.
The algorithm based on the idea that finding an element’s position in a sorted array.
Binary search works only on a sorted array. To use binary search, the array must be sorted first.
Binary Search Algorithm can be implemented in two ways are:
- Iterative Method
- Recursive Method
Implementation
Sample Code in C:
//Binary Search in C
#include<stdio.h>
int binarysearch(int arr[], int x, int low, int high)
{
//repeat until the pointers low and high meet each other
while(low <= high)
{
int mid = low + (high-low)/2;
if(arr[mid] == x)
return mid;
if(arr[mid] < x)
return mid + 1;
else
high = mid - 1;
}
return -1;
}
int main(void)
{
int data[] = {3, 15, 8, 1, 38, -2, 7};
int n = sizeof(data) / sizeof(data[0]);
int x = 3;
int result = binarysearch(data, x, 0, n-1);
if(result == -1)
printf("Element not found");
else
printf("Elements is found");
return 0;
Code language: C++ (cpp)
Output:
Element is found
Advantages
- Efficient on very big list.
- Can be implemented iteratively/recursively.
Disadvantages
- Interacts poorly with the memory hierarchy (more cache miss).
- Requires given list to be sorted.
- Due to random access of list element, needs arrays instead of linked list.
Time and Space Complexity
Time Complexity | |
Worst Case | O(log n) |
Best Case | O(1) |
Average Case | O(log n) |
Space Complexity | |
Worst Case | O(n) |
Applications
- Number guessing game
- Word lists/ search dictionary etc
Related:
Linear Search
Here, We discuss about Linear Search, their implementation in C, time and space complexity and…
Want to Contribute:-
If you like “To The Innovation” and want to contribute, you can mail your articles to 📧 [email protected]. See your articles on the main page and help other coders.😎