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.

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.

#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;

}

#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;

}

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

}

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

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.

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.

#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;

}

#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;

}

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

}

}

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

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 |

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

What is the difference between linear search and binary search?

The main distinction between these two methods lies in time complexity. The binary search takes O(logn), while the linear search takes O(n).

Which one, binary search versus linear search, operates faster?

The binary search algorithm operates faster as it doesn’t compare each element with the target element like linear search.

Which searching technique is best?

Searching efficiency makes the binary search algorithm the best.

What are the limitations of binary search?

The binary search algorithm can only work on sorted data.

What are two advantages of a linear search over a binary search?

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.

Privacy policy and Terms of use

© 2024 Hero Vired. All rights reserved