Data structures and algorithms have two techniques for searching through data. These are the Linear search algorithm and the Binary search algorithm. Both these algorithms have their own respective strengths and should be used in different situations. It is always good to learn such algorithms to find a particular element in the data set.
In this tutorial, we will cover linear search and binary search algorithms with code in various programming languages and the difference between both at the end of this guide.
What is Linear Search?
The linear search algorithm is one of the most common search techniques. It helps to locate a specific item within a set or sequential collection of data elements. When performing a linear search, each element from the dataset is compared with a given value, which returns the element’s address if there is a match.
This technique (linear) may be applied in cases where the volume of input values is relatively small, and the order of data is not sorted.
Linear Search Algorithm
Follow the below steps to implement the linear search algorithm.
- Use the loop and start at the array or list.
- Compare the target value with the current element.
- If the target value matches the current element, return the index of the current element.
- If the end of the list is reached without finding the target value, return -1.
Now, let’s look at example codes in different programming languages. In these codes, we will search the index of 10 in the [2, 5, 4, 3, 2, 10, 5] array. The code will return ‘5’ as it is an index of 10.
C
#include <stdio.h>
int linearSearch(int array[], int size, int tg) {
// Traverse through list
for (int k = 0; k < size; k++) {
// Compare each array element with target element
if (array[k] == tg) {
return k;
}
}
// When tg element is not found in array
return -1;
}
int main() {
int array[] = {2, 5, 4, 3, 2, 10, 5};
int target = 10;
int size = sizeof(array) / sizeof(array[0]);
printf(“%d\n”, linearSearch(array, size, target)); // Output: 5
return 0;
}
C++
#include <iostream>
using namespace std;
int linearSearch(int array[], int size, int tg) {
// Traverse through list
for (int k = 0; k < size; k++) {
// Compare each array element with target element
if (array[k] == tg) {
return k;
}
}
// When tg element is not found in array
return -1;
}
int main() {
int array[] = {2, 5, 4, 3, 2, 10, 5};
int target = 10;
int size = sizeof(array) / sizeof(array[0]);
cout << linearSearch(array, size, target) << endl; // Output: 5
return 0;
}
Java
public static int linearSearch(int[] array, int tg) {
// Traverse through list
for (int k = 0; k < array.length; k++) {
// Compare each array element with target element
if (array[k] == tg) {
return k;
}
}
// When tg element is not found in array
return -1;
}
public static void main(String[] args) {
int[] array = {2, 5, 4, 3, 2, 10, 5};
int target = 10;
System.out.println(linearSearch(array, target)); // Output: 2
}
Python
def linear_search(array, tg):
# Traverse through list
for k in range(len(array)):
# Compare each array element with target element
if array[k] == tg:
return k
# When tg element is not found in array
return -1
array = [2, 5, 4, 3, 2, 10, 5]
target = 10
print(linear_search(array, target)) # Output: 5
JavaScript
function linearSearch(array, tg) {
// Traverse through list
for (let k = 0; k < array.length; k++) {
// Compare each array element with target element
if (array[k] === tg) {
return k;
}
}
// When tg element is not found in array
return -1;
}
const array = [2, 5, 4, 3, 2, 10, 5];
const target = 10;
console.log(linearSearch(array, target)); // Output: 5
POSTGRADUATE PROGRAM IN
Multi Cloud Architecture & DevOps
Master cloud architecture, DevOps practices, and automation to build scalable, resilient systems.
What is Binary Search?
The binary search algorithm is more efficient than the linear search algorithm. The binary search algorithm is only implemented on the list if it is sorted in either increasing or decreasing order. It splits the list into 2 parts, checks whether the element is available in the left part or right part, and recursively splits each sub-part.
The binary search algorithm has lower time complexity as it doesn’t compare each element of the array with the target element. Due to high efficiency, it can be used to locate the element in large datasets.
Binary Search Algorithm
Follow the below steps to implement the binary search algorithm.
- Start with two pointers, one at the beginning (left) and one at the end (right) of the list.
- While left < right, follow the below steps:
- Calculate the middle index of the current sub-part of the array.
- Compare the target value with the middle element.
- If the target value matches the middle element, return the middle index.
- If the target value is less than the middle element, move the right pointer to the middle index – 1.
- If the target value is greater than the middle element, move the left pointer to the middle index + 1.
- If the target value is not found, return -1.
Here, we have covered the example of a binary search algorithm in various programming languages.
C
#include <stdio.h>
int binarySearch(int array[], int size, int tg) {
// Define pointers
int left = 0;
int right = size – 1;
while (left <= right) {
// Calculate middle element
int mid = left + (right – left) / 2;
// Compare the middle element with target element
if (array[mid] == tg) {
return mid;
}
if (array[mid] < tg) {
// To search in right sub-part
left = mid + 1;
} else {
// To search in left sub-part
right = mid – 1;
}
}
return -1;
}
int main() {
int array[] = {2, 5, 4, 3, 2, 10, 5};
int target = 10;
int size = sizeof(array) / sizeof(array[0]);
printf(“%d\n”, binarySearch(array, size, target)); // Output: 5
return 0;
}
Cpp
#include <iostream>
using namespace std;
class Solution {
public:
int binarySearch(int array[], int size, int tg) {
// Define pointers
int left = 0;
int right = size – 1;
while (left <= right) {
// Calculate middle element
int mid = left + (right – left) / 2;
// Compare the middle element with target element
if (array[mid] == tg) {
return mid;
}
if (array[mid] < tg) {
// To search in right sub-part
left = mid + 1;
} else {
// To search in left sub-part
right = mid – 1;
}
}
return -1;
}
};
int main() {
Solution sol;
int array[] = {2, 5, 4, 3, 2, 10, 5};
int target = 10;
int size = sizeof(array) / sizeof(array[0]);
cout << sol.binarySearch(array, size, target) << endl; // Output: 5
return 0;
}
Java
public class Solution {
public int binarySearch(int[] array, int tg) {
// Define pointers
int left = 0;
int right = array.length – 1;
while (left <= right) {
// Calculate middle element
int mid = left + (right – left) / 2;
// Compare the middle element with target element
if (array[mid] == tg) {
return mid;
}
if (array[mid] < tg) {
// To search in right sub-part
left = mid + 1;
} else {
// To search in left sub-part
right = mid – 1;
}
}
return -1;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] array = {2, 5, 4, 3, 2, 10, 5};
int target = 10;
System.out.println(sol.binarySearch(array, target)); // Output: 2
}
}
Python
class Solution:
def binary_search(self, array, tg):
# Define pointers
left = 0
right = len(array) – 1
while left <= right:
# Calculate middle element
mid = left + (right – left) // 2
# Compare the middle element with target element
if array[mid] == tg:
return mid
if array[mid] < tg:
# To search in right sub-part
left = mid + 1
else:
# To search in left sub-part
right = mid – 1
return -1
if __name__ == “__main__”:
sol = Solution()
array = [2, 5, 4, 3, 2, 10, 5]
target = 10
print(sol.binary_search(array, target)) # Output: 5
JavaScript
class Solution {
binarySearch(array, tg) {
// Define pointers
let left = 0;
let right = array.length – 1;
while (left <= right) {
// Calculate middle element
const mid = left + Math.floor((right – left) / 2);
// Compare the middle element with target element
if (array[mid] === tg) {
return mid;
}
if (array[mid] < tg) {
// To search in right sub-part
left = mid + 1;
} else {
// To search in left sub-part
right = mid – 1;
}
}
return -1;
}
}
const sol = new Solution();
const array = [2, 5, 4, 3, 2, 10, 5];
const target = 10;
console.log(sol.binarySearch(array, target)); // Output: 5
Differences Between Linear Search and Binary Search
| Feature | Linear Search | Binary Search |
| Algorithm | Checks each element one by one | Divides the search interval in half repeatedly |
| Complexity | O(n) | O(log n) |
| Data Requirement | Works on unsorted data | Requires data to be sorted |
| Performance | Slower for large datasets | Faster for large datasets |
| Best Use Case | Small or unsorted datasets | Large, sorted datasets |
| Implementation | Simple and easy to implement | More complex and requires sorting |
| Memory Usage | Low, uses a single loop | Low, uses a few pointers |
| Example Case | Finding a name in an unsorted list | Finding a number in a sorted list of integers |
| Worst Case | When the target is at the end or not present | When the target is at one of the ends |
| Iterative Steps | n steps for n elements | log n steps for n elements |
Conclusion
This blog has been able to explain linear search as well as binary search algorithms and their differences. Majorly, linear search can work with unsorted data as well as sorted data, while binary search can only be used on sorted data. Additionally, the time complexity for a binary is O(logn), whereas that of a linear one is O(n). However, both have the same space complexity. Also, small collections use the linear searching algorithm, and big datasets employ the binary searching algorithm.
What is the difference between linear search and binary search?
Which one, binary search versus linear search, operates faster?
Which searching technique is best?
What are the limitations of binary search?
What are two advantages of a linear search over a binary search?
Updated on July 8, 2024