Searching Algorithms

Searching is one of the most fundamental operations in computer science. Whether you are looking up a contact in a phone book, finding a product in an online store's inventory, or checking whether a username already exists in a database, some form of a searching algorithm is running behind the scenes. A searching algorithm is a step-by-step procedure that scans through a data structure — most commonly an array or list — to locate a target value, retrieve its position, or confirm that it does not exist in the collection. Choosing the right searching algorithm can mean the difference between a program that responds instantly and one that slows to a crawl under real-world data volumes.

The two most widely used searching algorithms for arrays and lists are linear search and binary search. They differ in their requirements, their strategies, and critically, their time complexity — the mathematical relationship between the size of the input and the number of steps the algorithm must perform. Understanding both algorithms deeply, including when to reach for each one, is an essential skill for any developer working with data.

Linear search is the simpler of the two. Its core idea is disarmingly straightforward: start at the first element of the array and inspect each element one by one, moving left to right, until you either find the target value or exhaust every element. Because it visits elements in sequence, it is sometimes called a sequential search. The beauty of linear search is its universality — it places no preconditions on the data. The array can be sorted or unsorted, it can contain strings or numbers or objects, and linear search will still work correctly.

The trade-off for that universality is efficiency. In the best case, the target is the very first element, and the algorithm finishes in a single step — O(1). In the average case, the target sits somewhere in the middle, requiring roughly n/2 comparisons. In the worst case — the target is the last element or is absent entirely — the algorithm must inspect all n elements, giving it a worst-case time complexity of O(n). For small arrays this is perfectly acceptable. But imagine searching through an array of one million elements: in the worst case, that is one million comparisons. For large datasets, linear search quickly becomes impractical.

Here is how linear search is implemented in JavaScript:

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i; // Target found — return its index
    }
  }
  return -1; // Target not found
}

// Example usage
const fruits = ["mango", "apple", "cherry", "banana", "grape"];

console.log(linearSearch(fruits, "banana")); // Output: 3
console.log(linearSearch(fruits, "kiwi"));   // Output: -1

Walking through this implementation step by step clarifies every design decision. The for loop begins at index 0 and runs as long as i is less than arr.length, ensuring every element is reachable. Inside the loop, the strict equality operator (===) is used intentionally: unlike loose equality (==), it checks both value and type, preventing subtle bugs where, for example, the number 3 would incorrectly match the string "3". When a match is found, the function immediately returns the index — there is no reason to keep searching once the target is located. If the loop completes without a match, the function returns -1, the conventional sentinel value in JavaScript (mirroring the behavior of built-in methods like Array.prototype.indexOf) to signal that the target was not found.

An alternative using forEach is also possible, though it requires a workaround since forEach cannot break early:

function linearSearchForEach(arr, target) {
  let result = -1;
  arr.forEach((element, index) => {
    if (element === target) {
      result = index;
    }
  });
  return result;
}

Notice that the for loop version is generally preferred for searching because it can return early the moment a match is found, whereas forEach always visits every element regardless. This early-exit behavior is a meaningful performance advantage when the target appears near the beginning of a large array.

Binary search takes a radically different approach and achieves dramatically better performance — but only under one strict condition: the array must be sorted. If the array is sorted in ascending order, binary search can exploit that structure to eliminate large swaths of the search space with every single comparison. Instead of checking elements one by one, it repeatedly halves the remaining search range.

The algorithm works as follows. Maintain two pointers, low and high, that define the boundaries of the current search range. Initially, low is 0 (the first index) and high is arr.length - 1 (the last index). Calculate the midpoint index as Math.floor((low + high) / 2). Compare the element at the midpoint to the target:

• If arr[mid] === target, the search is complete — return mid.
• If arr[mid] < target, the target must lie in the right half of the current range, so move low to mid + 1.
• If arr[mid] > target, the target must lie in the left half, so move high to mid - 1.

Repeat this process until either the target is found or low exceeds high, which means the boundaries have crossed and the target does not exist in the array.

Here is a concrete JavaScript implementation:

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    let mid = Math.floor((low + high) / 2);

    if (arr[mid] === target) {
      return mid; // Target found
    } else if (arr[mid] < target) {
      low = mid + 1; // Search the right half
    } else {
      high = mid - 1; // Search the left half
    }
  }

  return -1; // Target not found
}

// Example usage
const numbers = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91];

console.log(binarySearch(numbers, 23));  // Output: 5
console.log(binarySearch(numbers, 10));  // Output: -1

Let's trace through binarySearch(numbers, 23) to make the mechanics vivid. The array has 11 elements (indices 0–10), so low = 0, high = 10.

• Iteration 1: mid = Math.floor((0 + 10) / 2) = 5. arr[5] = 23. That equals the target — return 5. Done in one step!

Now trace binarySearch(numbers, 10) to see a miss:

• Iteration 1: low = 0, high = 10, mid = 5. arr[5] = 23. Since 23 > 10, set high = 4.
• Iteration 2: low = 0, high = 4, mid = 2. arr[2] = 8. Since 8 < 10, set low = 3.
• Iteration 3: low = 3, high = 4, mid = 3. arr[3] = 12. Since 12 > 10, set high = 2.
• Iteration 4: low = 3, high = 2. Now low > high — the loop exits. Return -1.

The algorithm determined that 10 is absent in just 3 comparisons against an 11-element array. With a linear search, the worst case would have required up to 11 comparisons. This difference becomes exponentially more significant as arrays grow. An array of 1,000,000 elements requires at most 20 comparisons with binary search (since log₂(1,000,000) ≈ 19.9), whereas linear search could require up to 1,000,000. This is what the time complexity notation O(log n) captures: every time the array size doubles, binary search only needs one additional comparison.

One subtle but important implementation detail is the midpoint calculation. Using Math.floor((low + high) / 2) avoids fractional (non-integer) indices that would break array access. In lower-level languages like Java or C, there is also a risk of integer overflow when low + high exceeds the maximum integer value — a safer formulation there would be low + Math.floor((high - low) / 2). In JavaScript, numbers are 64-bit floating-point, so overflow is not a practical concern for typical array sizes, but it is good practice to know about this nuance.

Comparing the two algorithms side by side sharpens the decision of when to use each:

• Time complexity: Linear search is O(n) in the worst case. Binary search is O(log n) in the worst case. For large datasets, this is an enormous difference. Searching 1 billion elements linearly could require 1 billion steps; binary search would need at most 30.
• Preconditions: Linear search works on any array — sorted, unsorted, mixed types. Binary search requires a sorted array. If your data is unsorted and sorting it first would cost O(n log n), you must weigh whether the subsequent search savings justify that upfront cost. For a single search on unsorted data, linear search is often the better choice. For many repeated searches on the same dataset, sorting once and using binary search repeatedly pays off decisively.
• Implementation complexity: Linear search is trivial to write and almost impossible to get wrong. Binary search, while not complex, has several edge cases — off-by-one errors in pointer updates and the loop condition — that make careful implementation important.
• Practical use cases: Linear search is ideal for small arrays, unsorted data, or situations where simplicity and readability outweigh raw performance. Binary search shines in performance-critical applications: searching large sorted price lists, looking up words in a dictionary, implementing autocomplete features, or any scenario where the data is already maintained in sorted order.

It is also worth noting that JavaScript's standard library provides built-in methods that internally use these strategies. Array.prototype.indexOf and Array.prototype.find both perform linear searches. When working with sorted data where you need maximum performance, implementing binary search explicitly — or using a library that provides it — gives you the O(log n) guarantee. Understanding the algorithms behind these abstractions empowers you to make informed choices about when the built-in methods are sufficient and when you need to reach for something more efficient.