Linear & Binary Searches

What Are Search Algorithms?

Search algorithms find specific data in a list or database.

The two most common search algorithms are linear search (O(n)) and binary search (O(log n)).

Comparison of Linear and Binary Search

Algorithm Time Complexity Best Use Case Visualisation
Linear Search O(n) – scans each element in turn Use when data is unsorted or the dataset is small.
Sample scenario: Checking if "CS101" appears in today’s 15-item attendance list that hasn’t been sorted. 		Visualisation
Binary Search O(log n) – halves search range each step Use when data is sorted (ascending or descending, known order).
Sample scenario: Finding a username in an alphabetically sorted roster of 5,000 students. 		Visualisation

Example: Implementing Search Algorithms

Algorithm Steps

  • Linear Search:
    1. Start at index 0.
    2. Compare the element at the current index to the target.
    3. If they match, return the current index.
    4. Otherwise, move to the next index.
    5. If you reach the end without finding the target, return -1.
  • Binary Search:
    1. Initialise left to 0 and right to len(arr) - 1 (or arr.length - 1 in Java).
    2. While left ≤ right:
    3. Calculate mid = (left + right) // 2 (or equivalent formula in Java).
    4. If arr[mid] equals the target, return mid.
    5. If arr[mid] is less than the target, set left = mid + 1; otherwise, set right = mid - 1.
    6. If the loop finishes without finding the target, return -1.

Linear Search Implementation

Linear Search

def linear_search(arr, target):
  for i in range(len(arr)):
    if arr[i] == target:
      return i # index found
  return -1 # not found

numbers = [5, 3, 8, 2, 7]
print("Index:", linear_search(numbers, 7))

Linear Search

public class LinearSearch {
  public static int search(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
      if (arr[i] == target) return i;
    }
    return -1;
  }

  public static void main(String[] args) {
    int[] numbers = {5, 3, 8, 2, 7};
    System.out.println("Index: " + search(numbers, 7));
  }
}

Binary Search Implementation

Binary Search

def binary_search(arr, target):
  left, right = 0, len(arr) - 1
  while left <= right:
    mid = (left + right)//2
    if arr[mid] == target:
      return mid
    elif arr[mid] < target:
      left = mid + 1
    else:
      right = mid - 1
  return -1

numbers = [2, 3, 5, 7, 8]
print("Index:", binary_search(numbers, 7))

Binary Search

import java.util.Arrays;

public class BinarySearch {
  public static int search(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
      int mid = left + (right - left)/2;
      if (arr[mid] == target) return mid;
      if (arr[mid] < target) left = mid + 1;
      else right = mid - 1;
    }
    return -1;
  }

  public static void main(String[] args) {
    int[] numbers = {2, 3, 5, 7, 8};
    System.out.println("Index: " + search(numbers, 7));
  }
}

Choosing the Right Search Algorithm

  • Use Linear Search when:
    • Data is unsorted.
    • Dataset is small.
    • Implementation speed matters more than search speed.
  • Use Binary Search when:
    • Data is sorted.
    • Dataset is large or many searches will (could) be performed.

Efficiency-Based Scenarios

Pick the technique based on how the data is organised: if the target field is sorted or indexed, use a logarithmic approach; if it is unsorted, use a linear scan.

Question Data / Index Efficient Choice Sample Scenario
Name → Phone Directory is sorted by name (or has a name index) Binary Search (O(log n)) A student directory is alphabetically ordered. You look up “Nguyen” and narrow the range quickly by halving the search window each step until the record is found.
Phone → Name Directory is not sorted by phone (only sorted/indexed by name) Linear Search (O(n)) You have a caller’s number but the CSV is ordered by last name. Because phone numbers aren’t in order, you scan each row until you hit the exact match-fine for one-off lookups, slower for many.
Phone → Name Directory is sorted by phone (or has a phone index) Binary Search (O(log n)) The school system maintains a secondary index on phone numbers. You jump directly to the relevant block and pinpoint the record in a handful of steps instead of scanning the whole file.

Rule of thumb: don’t force binary search on unsorted data-either sort or use an index first; otherwise, prefer a simple linear scan.

Avoiding Common Errors

  • Binary Search on Unsorted Data: Always sort before searching.
  • Missing Base Case in Recursion: Ensure recursive search terminates.
  • Off-by-One Errors: Double-check loop and index boundaries.

 Key Takeaways

  • Linear search scans each element (O(n)), simple but slow on large data.
  • Binary search divides search range in half (O(log n)), fast on sorted data.
  • Choose based on data order and efficiency requirements.
  • Both Python and Java support these search methods with clear implementations.