In this algorithm we will exaplain the most famous algorithm is Binary search. Here we explain through example then do program.
- According to the name, we clear that it is something two things.
- This type of searching occurs in a sorted array. Otherwise, it will not work properly.
- STEP 1:Lets take an unsorted array of 6 elements.
- STEP 2: We sort the array in increasing order.
- STEP 3: Lets we take search 10 in this array. So we divide the array from the middle. Here the middle term is 4, we first compare the middle term with the search element. If the Middle term is less than the search element (4 < 10). So here in the given figure, the first half of the array leaves. Because our search element come under the range of second half of the array.
- STEP 4: Second half of array we again divide the array in two half and compare the middle element with the search element. if the middle term is equal search element, then we find search elements. otherwise, we repeat step 3 until the found element. In the given figure, we found element 10 matches with search element.
- Time Complexity of the Binary Searching is 0(Log N), N is the number of elements in the array.
Example: Binary Search Program in C++
#include <iostream>
using namespace std;
int binary_search(int arr[],int first,int last,int search)
{
while(first<last)
{
int middle= first + (last - first)/2;
//here we compare with middle term if find then return index of array
if(arr[middle]==search)
{
return middle;
}
//If middle term smaller than search element ,then search in right subarray
if(arr[middle]<search)
{
first = middle +1;
}
//If middle term greater than search element ,then search in left subarray
if(arr[middle]>search)
{
last = middle - 1;
}
}
return 0;
}
int main()
{
int arr[6]={1,2,4,5,10,12};
int search = 10;
int n = 6;
cout<<"Search element at index "<<binary_search(arr,0,n-1,10);
return 0;
}
Output :Search element at index 4
For more detail about Binary Search.Article Related to searching Linear Searching
More Interesting article..