School of Computing
SRM IST, Kattankulathur – 603 203
A STUDY REPORT
on
Linear Search vs Binary Search
Submitted by
NANDAN CHOWDHURY [Reg No: RA2111003010922]
FARAZ QUASSEM [Reg No: RA2111003010953]
for the course
18CSC204J - Design and Analysis of Algorithms
Under the guidance of
Dr .M.L.Sworna Kokila
in partial fulfilment for the award of
the degree of
Bachelor of Technology
in
Computer Science and Engineering
of
Faculty of Engineering and Technology
Introduction:
Searching is one of the most common operations in
computer science, and it involves finding a particular
element or value from a given set of data. There are
various techniques for searching, each with its own
advantages and disadvantages. In this comparative
study, we will discuss two of the most commonly used
searching techniques: Naive method (Linear Search)
and Divide & Conquer (Binary Search). We will provide
an overview of each technique, followed by its
algorithm and complexity analysis.
1. Naive Method - Linear Search:
Linear search, also known as sequential search, is the
simplest method of searching. It involves searching
through each element of the given data set until the
desired element is found. This technique is useful for
small data sets or unsorted data.
Algorithm:
1.Start from the first element of the array.
2.Compare the current element with the desired
element.
3.If the current element is equal to the desired
element, return the index of the current element.
4.If the current element is not equal to the desired
element, move to the next element.
5.Repeat steps 2-4 until the end of the array is
reached or the desired element is found.
Pseudocode:
function linearSearch(array, element):
for i = 0 to length(array) – 1
if array[i] == element
return i
return -1
Example:
Time Complexity Analysis:
The Best Case occurs when the target element is
the first element of the array. The number of
comparisons, in this case, is 1. So, the time
complexity is O(1).
The Average Case: On average, the target element
will be somewhere in the middle of the array. The
number of comparisons, in this case, will be N/2. So,
the time complexity will be O(N) (the constant being
ignored).
The Worst Case occurs when the target element is
the last element in the array or not in the array. In
this case, we have to traverse the entire array, and
so the number of comparisons will be N. So, the time
complexity will be O(N).
Applications:
Sequential data processing
Simple database queries
Spell checkers
2. Divide & Conquer Technique - Binary
Search:
A divide and conquer algorithm is a strategy of
solving a large problem by
1. breaking the problem into smaller sub-problems
2. solving the sub-problems, and
3. combining them to get the desired output.
Binary search is a more efficient searching technique
that utilizes the divide and conquer approach. It
involves dividing the data set into two halves and
searching for the desired element in one of the halves.
This technique is useful for large data sets and sorted
data.
Algorithm:
1. Initialize start and end variables to the first and
last indices of the array, respectively.
2. Calculate the mid index by taking the average of
start and end.
3. Compare the desired element with the element at
the mid index.
4. If the desired element is equal to the element at
the mid index, return the mid index.
5. If the desired element is less than the element at
the mid index, set end to mid-1 and repeat steps 2-
4.
6. If the desired element is greater than the element
at the mid index, set start to mid+1 and repeat
steps 2-4.
7. Repeat steps 2-6 until the desired element is found
or start is greater than end.
Pseudocode:
function binarySearch(array, element, start, end):
if start > end
return -1
mid = (start + end) / 2
if array[mid] == element
return mid
else if array[mid] > element
return binarySearch(array, element, start, mid - 1)
else
return binarySearch(array, element, mid + 1, end)
Example:
Time Complexity Analysis:
Recurrence relation-> T(n)=T(n/2)+1
1st step=> T(n)=T(n/2) + 1
2nd step=> T(n/2)=T(n/4) + 1 ……[ T(n/4)=
T(n/2^2) ]
3rd step=> T(n/4)=T(n/8) + 1 ……[ T(n/8)= T(n/2^3)
]
.
.
kth step=> T(n/2^k-1)=T(n/2^k) + 1*(k times)
So, T(n) = T(n/2^k) + k ---> eq(final)
=> n/2^k= 1
=> n=2^k
=> log n=k
T(n) = T(1) + log n
T(n) = O(log n)
Applications:
Search engines
Computer games
Sorting algorithms
Differences:
Conclusion:
In conclusion, both linear search and binary search
techniques are useful for searching elements in data
sets. However, their efficiency depends on the size and
structure of the data set. Linear search is useful for
small data sets or unsorted data, while binary search is
useful for large data sets and sorted data. Binary
search has a much better time complexity of O(log n)
compared to the linear search's O(n) time complexity.
