Linear & Binary Search

Searching is the process of finding the position or existence of a specific element within a collection of data.

1. Linear Search

The most basic searching algorithm. It simply iterates through every single element in the array one by one until it finds the target.

When to use it: When the array is unsorted or very small. It is the only option for unsorted data.

• Time Complexity: $O(N)$
• Space Complexity: $O(1)$

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

2. Binary Search

A vastly superior search algorithm that drastically cuts down the search space. However, it ONLY works if the array is already sorted.

How it works:

1. Check the middle element of the array.
2. If it is the target, return its index.
3. If the target is smaller than the middle element, the target must be in the left half. Discard the right half.
4. If the target is larger, discard the left half.
5. Repeat the process on the remaining half.

• Time Complexity: $O(\log N)$
• Space Complexity: $O(1)$ (Iterative) or $O(\log N)$ (Recursive call stack)

function binarySearch(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    // Avoid integer overflow bug in other languages: left + (right - left) / 2
    const mid = Math.floor((left + right) / 2); 
    
    if (arr[mid] === target) {
      return mid; // Found!
    }
    if (arr[mid] < target) {
      left = mid + 1; // Target is to the right
    } else {
      right = mid - 1; // Target is to the left
    }
  }
  
  return -1; // Not found
}

Variations of Binary Search

Binary Search isn't just for finding an exact number. It is heavily used in algorithmic problem-solving to find Bounds or to search over a "Solution Space".

1. Finding Lower/Upper Bounds

If an array contains duplicates (e.g., [1, 2, 2, 2, 3]), standard Binary Search might return any index pointing to 2. If you need the first occurrence (Lower Bound) or last occurrence (Upper Bound), you modify the if (arr[mid] === target) condition to keep searching left or right instead of immediately returning.

2. Binary Search on Answer

Sometimes you are asked to find the "minimum capacity of a ship" or "minimum speed to eat bananas". The possible answers range from 1 to Max. Because this range is perfectly sorted (1, 2, 3, 4...), you can binary search the answers themselves!

function minSpeedToEatBananas(piles: number[], h: number): number {
  // Binary searching the actual speed (K)
  let left = 1;
  let right = Math.max(...piles); // Max possible speed
  let result = right;

  while (left <= right) {
    const k = Math.floor((left + right) / 2);
    
    // Helper function to check if speed 'k' is valid
    if (canFinishInTime(piles, h, k)) {
      result = k;      // This works, but maybe we can go slower?
      right = k - 1;   // Search slower speeds (Left)
    } else {
      left = k + 1;    // Too slow! Search faster speeds (Right)
    }
  }
  return result;
}