Avail your 25% scholarship. Chat now.

# The Difference between Linear Search and Binary Search

Internship Assurance
DevOps & Cloud Engineering

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.

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(“%dn”, 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

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(“%dn”, 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

Internship Assurance
DevOps & Cloud Engineering

 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.

FAQs
The main distinction between these two methods lies in time complexity. The binary search takes O(logn), while the linear search takes O(n).
The binary search algorithm operates faster as it doesn’t compare each element with the target element like linear search.
Searching efficiency makes the binary search algorithm the best.
The binary search algorithm can only work on sorted data.
The linear search is easy to implement and can also work with unsorted data.

Book a free counselling session

Get a personalized career roadmap

Get tailored program recommendations

Explore industry trends and job opportunities

Programs tailored for your success

Popular

Data Science

Technology

Finance

Management

Future Tech

Upskill with expert articles
View all
Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.

Blogs
Reviews
Events
In the News