A Comparative Analysis of the Efficiencies of Binary and Linear Search Algorithms
In the world of computer science,
searching for data is a basic but very important task. Two of the most commonly
used search methods are Linear Search and Binary Search. In this
blog, we will explain how both algorithms work, compare their efficiency, and
provide code examples with outputs.
What
is Linear Search?
Linear
Search is the simplest
search algorithm. It is a sequential searching algorithm where we start from
one end and checks every element of the list until the desired element is
found.
Linear
Search Working:
The following steps are followed to
search for an element k = 1 in the list below. 
Array to be searched
for
1.
Start from the first element,
compare k with each element x. 
Compare with each element
2.
If x == k, return the index. 
Element found
3. Else, return not found.
C++
Code for Linear Search:
#include
<iostream>
using namespace
std;
int
linearSearch(int arr[], int n, int x) {
for(int i = 0; i < n; i++) {
if(arr[i] == x) {
return i; // element found at index
i
}
}
return -1; // element not found
}
int main() {
int arr[] = {2, 4, 0, 1, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 1;
int result = linearSearch(arr, n, x);
if(result != -1)
cout << "Element found at
index " << result << endl;
else
cout << "Element not
found." << endl;
return 0;
}
Expected
Output:
Element found at
index 3
What
is Binary Search?
Binary
Search is a searching algorithm,
but it works for finding an element’s position in a sorted array. It
reduces the search area by half each time. In this approach, the element is
always searched in the middle of a portion of an array.
Binary
Search Working:
Binary
search algorithm can be implemented in
two ways which are discussed below.
1. Iterative
Method
2. Recursive
Method
The recursive
method follows the divide and conquer approach.
The general
steps for both methods are discussed below.
1.
The
array in which searching is to be performed is:
Initial array
Let x = 4 be the element to be searched.
2. Set two
pointers low and high at the lowest and the highest
positions respectively.
setting pointers
3.
Find
the middle position mid of the array ie. mid = (low +
high)/2 and arr[mid] = 6. 
mid-element
4.
If x
== arr[mid], then return mid. Else, compare the element to be searched
with arr[mid].
5.
If x
> arr[mid], compare x with the middle element of the elements on
the right side of arr[mid]. This is done by
setting low to low = mid + 1.
6.
Else,
compare x with the middle element of the elements on the left side
of arr[mid]. This is done by setting high to high = mid -1.
finding
mid- element
7.
Repeat
steps 3 to 6 until low meets high. 
mid-element
8.
X=
4 is found.
found
C++
Code for Binary Search:
#include
<iostream>
using namespace
std;
int
binarySearch(int arr[], int n, int x) {
int low = 0, high = n - 1;
while(left <= high) {
int mid = (low + high) / 2;
if(x == arr[mid] )
return mid;
else if(x > arr[mid])
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int main() {
int arr[] = { 3, 4, 5, 6,
7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 4;
int result = binarySearch(arr, n, x, low,
high);
if(result != -1)
cout << "Element found at
index is : " << result << endl;
else
cout << "Element not
found." << endl;
return 0;
}
Expected
Output:
Element found at
index is : 1 .
Comparison
Table: Binary vs Linear Search
|
Feature |
Linear Search |
Binary Search |
|
Data Requirement |
Works on unsorted data |
Requires sorted data |
|
Time Complexity (Best) |
O(1) |
O(1) |
|
Time Complexity (Average) |
O(n/2) |
O(log n) |
|
Time Complexity (Worst) |
O(n) |
O(log n) |
|
Simplicity |
Very simple to implement |
Slightly complex |
|
Efficiency |
Slower for large data |
Much faster for large sorted data |
Algorithm:-
Algorithm
SmartSearch(arr, n, key)
If n ≤ 10 OR NOT isSorted(arr, n) Then
method ← "Linear Search"
return linearSearch(arr, n, key)
Else
method ← "Binary Search"
return binarySearch(arr, n, key)
EndIf
EndAlgorithm
Algorithm
isSorted(arr, n)
For i ← 1 to n - 1
If arr[i] < arr[i - 1] Then
return False
EndFor
return True
EndAlgorithm
Algorithm
linearSearch(arr, n, key)
For i ← 0 to n - 1
If arr[i] = key Then
return i
EndFor
return -1
EndAlgorithm
Algorithm binarySearch(arr,
n, key)
left ← 0, right ← n - 1
While left ≤ right
mid ← (left + right) / 2
If arr[mid] = key Then
return mid
Else If arr[mid] < key Then
left ← mid + 1
Else
right ← mid - 1
EndWhile
return -1
EndAlgorithm
Expected
Output1:- [for more than 10 elements]
Enter the
element you want to search: 30
Result:
Element found at
index 2 using Binary Search.
Output2:
[ for less than 10 element ]
Enter the element
you want to search: 60
Result:
Element found at
index 6 using Binary Search.
Conclusion
- If you are working with small
or unsorted data, Linear Search is easy and practical.
- If you are handling large
datasets that are sorted, Binary Search is far more efficient.
- Always choose your search method
based on the nature of the data and the performance needs of your
application.
Reference:
Comments
Post a Comment