Array Searching

Searching is the process of finding a specific element in an array.

1. Linear Search

Linear Search iterates through the array from start to end, checking each element.

• Time Complexity: O(N)
• Space Complexity: O(1)
• Condition: Works on any array (sorted or unsorted).

public int linearSearch(int[] nums, int target) {
  for (int i = 0; i < nums.length; i++) {
    if (nums[i] == target) {
      return i;
    }
  }
  return -1;
}

2. Binary Search

Binary Search is a much faster algorithm but requires the array to be sorted. It repeatedly divides the search interval in half.

• Time Complexity: O(log N)
• Space Complexity: O(1) (Iterative)
• Condition: Array must be sorted.

[!NOTE] We cover Binary Search in depth in Module 10: Sorting & Searching.

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

---

3. Deep Dive Strategy Lab: Array Searching

Intuition Through Analogy

Think of this chapter like organizing items on a warehouse shelf. The goal is not to memorize a fixed trick, but to repeatedly answer:

1. What is the bottleneck?
2. Which constraint dominates (time, memory, latency, correctness)?
3. Which representation makes the bottleneck easier to eliminate?