What Is Linear and Binary Search in Data Structure?

//

Larry Thompson

In data structure, searching is a fundamental operation that involves finding a specific element in a collection of data. Two popular search algorithms used in data structures are linear search and binary search. Let’s understand what these algorithms are and how they work.

Linear Search

Linear search is a simple searching algorithm that sequentially checks each element in a list until it finds the desired element or reaches the end of the list. It is also known as sequential search.

To perform a linear search, we start from the beginning of the list and compare each element with the Target element. If the Target element is found, we return its index; otherwise, we continue searching until we either find the Target or reach the end of the list.

Here’s an example implementation of a linear search algorithm:


function linearSearch(arr, Target) {
    for(let i = 0; i < arr.length; i++) {
        if(arr[i] === Target) {
            return i;
        }
    }
    return -1;
}

A linear search has a time complexity of O(n), where n is the number of elements in the list. This means that in the worst-case scenario, where the desired element is at the end or not present at all, it may need to compare every element in the list.

Binary Search

Binary search is an efficient searching algorithm used on sorted lists or arrays. It follows a divide-and-conquer approach and reduces the search space by half with each iteration.

To perform a binary search, we start by comparing the Target element with the middle element of the sorted list. If they are equal, we have found our desired element. If not, we determine whether to continue searching in either the left or right half of the list based on the comparison result.

Here's an example implementation of a binary search algorithm:


function binarySearch(arr, Target) {
    let left = 0;
    let right = arr.length - 1;
    
    while(left <= right) {
        let mid = Math.floor((left + right) / 2);
        
        if(arr[mid] === Target) {
            return mid;
        }
        
        if(arr[mid] < Target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

A binary search has a time complexity of O(log n), where n is the number of elements in the sorted list. It repeatedly divides the search space in half, making it significantly faster than linear search for large lists.

Key Differences

  • Performance: Linear search has a time complexity of O(n), while binary search has a time complexity of O(log n).
  • Data Requirement: Linear search works on both sorted and unsorted lists, while binary search requires a sorted list.
  • Implementation: Linear search is simple to implement, whereas binary search requires careful handling of indices and sorting beforehand.

In conclusion, both linear and binary searches are important algorithms in data structure. Linear search is suitable for small lists or unsorted data, while binary search offers better performance on large sorted lists. Understanding these algorithms allows you to choose the most appropriate one for your specific requirements.

Discord Server - Web Server - Private Server - DNS Server - Object-Oriented Programming - Scripting - Data Types - Data Structures

Privacy Policy