The Difference between Linear Search and Binary Search

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(“%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

Differences Between Linear Search and Binary Search

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.