Not even a single day pass, when we do not have to search for something in our day to day life, car keys, books, pen, mobile charger and what not. Same is the life of a computer, there is so much data stored in it, that whenever a user asks for some data, computer has to search it's memory to look for the data and make it available to the user. And the computer has it's own techniques to search through it's memory fast, which you can learn more about in our Operating System tutorial series.
What if you have to write a program to search a given number in an array? How will you do it?
Well, to search an element in a given array, there are two popular algorithms available:
Linear search is a very basic and simple search algorithm. In Linear search, we search an element or value in a given array by traversing the array from the starting, till the desired element or value is found.
It compares the element to be searched with all the elements present in the array and when the element is matched successfully, it returns the index of the element in the array, else it return -1
.
Linear Search is applied on unsorted or unordered lists, when there are fewer elements in a list.
We will implement the Linear Search algorithm in the next tutorial.
Binary Search is used with sorted array or list. In binary search, we follow the following steps:
Binary Search is useful when there are large number of elements in an array and they are sorted.
So a necessary condition for Binary search to work is that the list/array should be sorted.