Search algorithms are used in programming to quickly find element of our desire from an array or list of values.The goal of search algorithm is to find the element with less number of steps thus reducing the time taken for it.In this tutorial we are going to take a look at Binary search algorithm and how to use it in our code.Here are some of the Algorithms we have covered earlier in our website.
Binary search Algorithm:
Binary search is an algorithm widely used to find an element in an array.The important condition for Binary search to work is that the array should be sorted in ( ascending, descending or by any other means).Binary search Algorithm works by repeatedly dividing the given array in halfand search through the list for the required element.The important advantage in using Binary search is that it reduces the number of searches by dividing the array in half thus reducing the time required for finding the element we are looking for.
Explanation:
Consider the following values in an array and we need to find the number 43 from the given array using Binary Search Algorithm
We need to find the number that is in the middle position of the array
Now compare center element of the array 15 against our required number 43.15 is lesser than than 43 and therefore as a sorted array we can conclude that our element 43 is in the higher side of array and lower half of the array can be safely eliminated from search.
Now the new array that we have here is
The middle position of this array is 25 now, comparing 25 with the required value 43 we can discard the lower half of the the array since 43 is greater than 25.
Now we are left with only element in the array.Comparing with the required value 43 a match is found and the search is complete now.The position of this element is returned by the program now.
How to implement Binary search Algorithm:
- Sort the given array in ascending order or descending order, you can use any sorting algorithm for this job.
- Find the middle position of the array and check whether it matches with the given number.
- If there is a match, return the position of the element, if not divide the array in to two parts.
- Based on the type of sorting eliminate any one half of the array.
- Compare the middle position of the new array with our desired value
- Repeat this process until our desired value is found or the array is empty.
Code:
#include
int Binarysearch(int arr[], int size, int search) { int Upper_Limit = (size - 1)!int Lower_Limit = 0!int Mid_Pos!while (Upper_Limit >= Lower_Limit) { Mid_Pos = (Upper_Limit + Lower_Limit) / 2!if (arr[Mid_Pos] == search) { // when the element presents in the middle return Mid_Pos + 1!} else if (arr[Mid_Pos] > search) { // If element is smaller than middle value, left side of array is selected Upper_Limit = (Mid_Pos - 1)!} else { // If element is bigger than middle value, right side of array is selected Lower_Limit = (Mid_Pos + 1)!} } return -1!// return -1 if no match found } int main(void) { int arr[] = {5, 7, 15, 25, 43}!//given sorted array int size = sizeof(arr) / sizeof(arr[0])!//size of the array int search = 43!//value to be searched int result = Binarysearch(arr, size, search)!//returns the position of the element in the array if (result == -1) { printf("Number is not present in this array.")!} else { printf("Number is present at the Index : %d", result)!} return 0!}
Where to use Binary search Algorithm:
Binary Search Algorithm works really well with a large number of elements and it is much faster than other search algorithm.However if you want to implement this, the array elements must be sorted.
Activity:
In order to understand this Algorithm better, try this below activity
- Write a program of any language to take array input of 10 values.The code should first sort it in ascending order and then the given value should be searched using Binary search technique
Hope this tutorial has helped you to learn this search algorithm and improves your code.Do share the result of the above activity with us.Post your questions, feedback in the below comment box, we will be happy to help you.
