Linear vs Binary Search

Searching is a fundamental task when working with data structures. Linear Search and Binary Search are two approaches, each with their own advantages and disadvantages in different scenarios.

Linear Search

Linear search is the simplest search algorithm; it examines each element sequentially from the beginning to the end of an array or list to find a target value. Its average and worst-case time complexity is O(n), which occurs when the element is not in the list or is located at the very end. Its best-case time complexity is O(1), occurring when the target element is found at the first position.

While its advantages are that it is easy to implement and able to work with both sorted and unsorted data, its main disadvantage is that it is slow on large data sets.

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

Binary Search

Binary search is an algorithm that searches the target element by repeatedly splitting the array in half.

• It checks the middle element.
• If the value is smaller than the middle one, it looks in the left half; if it is larger, it looks in the right half.
• This process continues until the element is found or the subarray is empty.

Its best, average, and worst-case time complexity is O(log n), meaning it remains very fast even on large datasets. However, its main disadvantage is that it cannot be used with unsorted data.

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

Comparison of Linear and Binary Search

Here is a comparison table of linear and binary search.

In conclusion, linear search is a simple and effective algorithm for searching in small datasets or when working with unsorted data, while binary search is a more efficient algorithm for searching in large datasets or when working with sorted data.

Thanks for reading this article.