In this article, We will see an important concept of Data structure i.e., Binary Search. after going through the whole article you will come to know about Binary Search, How to implement binary search, Working process and the binary search complexities.
What is Searching ?
Searching is the process of finding the element in the list (Array, linked-list, Stack, heap etc.). There are two types of searching process i.e., Linear Search and Binary Search. In this article, we will see Binary search in detail.
What is Binary Search Algorithm ?
Binary Search is the search which works efficiently with the sorted list. Hence, if we want to work with the binary search, then firstly we have to ensure whether it is sorted or not. “Binary Search works on divide and rule approach, in which the whole list (on which we want to apply algorithm) is divided into two halves.
Working Procedure (Algorithm)
Step 1 : Compare the searching element with the Middle element of the List.
Step 2 : If it is equal to the Searching element then it will terminate and send the index of the same.
Step 3 : If the middle one is not equal to Searching element. Then,
Condition 1 : Compare if it is smaller than Searching element, then traverse left side again apply divide and rule.
Condition 2 : Compare if it is Greater than Searching element, then traverse Right side and again apply divide and rule.
Step 4 : It will be continue until the whole list traversed.
Binary Search in C++
#include<iostream>
using namespace std;
int main()
{
int n;
cout<<“Enter size of array: “;
cin>>n;
int i, arr[n], num, first, last, middle;
cout<<“Enter Elements (in ascending order): “;
for(i=0; i<n; i++)
cin>>arr[i];
cout<<“\nEnter Element to be Search: “;
cin>>num;
first = 0;
last = 9;
middle = (first+last)/2;
while(first <= last)
{
if(arr[middle]<num)
first = middle+1;
else if(arr[middle]==num)
{
cout<<“\nThe number, “<<num<<” found at Position “<<middle+1;
break;
}
else
last = middle-1;
middle = (first+last)/2;
}
if(first>last)
cout<<“\nThe number, “<<num<<” is not found in given Array”;
cout<<endl;
return 0;
}
Time and Space complexity of Binary Search
Time Complexity in Binary Search
- Best Case : O(1)
- Average Case : O(log N)
- Worst Case : O(log N)
Space Complexity in Binary Search
- Space complexity : O(1)
Advantages of Binary Search
- Binary Search is more Efficient than Linear Search.
- It is good to use it for Large datasets.
- Faster than Linear Search.
Disadvantages of Binary Search
- Array on which you want to apply algorithm, should be sorted.
- Binary search requires that the data structure being searched be stored in contiguous memory locations.
Hope all your doubt will be Cleared after reading the whole Article Carefully. You can connect with us using the following links :
Important Links
| Join WhatsApp | Click Here |
| Join Telegram | Click Here |
| Join Twitter (X) | Click Here |
| Join Instagram | Click Here |
