Unit II
Searching and Sorting
Algorithms
Introduction to Searching Algorithms
• Searching Algorithms are designed to check for an
element or retrieve an element from any data
structure where it is stored.
• Searching is the process of finding the location of
required data in the given list of objects.
• To search an element in a given array, there are some
popular algorithms available:
1. Linear Search
2. Binary Search
3. Fibonacci 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.
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
• It is great to search through large sorted
arrays.
• It has a time complexity of O(log n) which is a
very good time complexity.
• It has a simple implementation.
• Time Complexity of Binary SearchO(log n)
• When we say the time complexity is log n, we
actually mean log2 n, although the base of the
log doesn't matter in asymptotic notations,
but still to understand this better, we generally
consider a base of 2.
• Let's first understand what log2(n) means.
• Expression: log2(n)
• ---------------
For n = 2:
log2(21) = 1
Output = 1
• ---------------
For n = 4
log2(22) = 2
Output = 2
• ---------------
For n = 8
log2(23) = 3
Output = 3
• ---------------
For n = 256
log2(28) = 8
Output = 8
• ---------------
For n = 2048
log2(211) = 11
Output = 11
• Now that we know how log2(n) works with
different values of n, it will be easier for us to
relate it with the time complexity of the binary
search algorithm and also to understand how
we can find out the number of steps required
to search any number using binary search for
any value of n.
