studytonight.com
We are Hiring!                  Sign in
See the Tutorial List

Introduction to Searching Algorithms

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:

  1. Linear Search
  2. Binary Search

Linear Search

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.

Features of Linear Search Algorithm

  1. It is used for unsorted and unordered small list of elements.
  2. It has a time complexity of O(n), which means the time is linearly dependent on the number of elements, which is not bad, but not that good too.
  3. It has a very simple implementation.

We will implement the Linear Search algorithm in the next tutorial.

Binary Search

Binary Search is used with sorted array or list. In binary search, we follow the following steps:

  1. We start by comparing the element to be searched with the element in the middle of the list/array.
  2. If we get a match, we return the index of the middle element.
  3. If we do not get a match, we check whether the element to be searched is less or greater than in value than the middle element.
  4. If the element/number to be searched is greater in value than the middle number, then we pick the elements on the right side of the middle element(as the list/array is sorted, hence on the right, we will have all the numbers greater than the middle number), and start again from the step 1.
  5. If the element/number to be searched is lesser in value than the middle number, then we pick the elements on the left side of the middle element, and start again from the step 1.

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.

Features of Binary Search

  1. It is great to search through large sorted arrays.
  2. It has a time complexity of O(log n) which is a very good time complexity. We will discuss this in details in the Binary Search tutorial.
  3. It has a simple implementation.