[AlgoMastery]
Topics›Array›Search in Array
📖

Search in Array

Array
~20 min read
5 practice problems

Overview

Search in Array involves finding elements or positions in arrays efficiently. The most common technique is Binary Search, which reduces search space by half at each step, achieving O(log n) time complexity for sorted arrays.

Search problems vary by:

  • Sorted vs unsorted arrays
  • Rotated sorted arrays
  • 2D arrays (matrices)
  • Search space (value, position, range)
  • Duplicates handling

Search in array is particularly useful for:

  • Finding target values
  • Finding insertion positions
  • Range queries
  • Peak finding
  • Search space reduction

Pattern 1: Binary Search (Basic)

Search target in sorted array.

function binarySearch(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return -1;
}

Time: O(log n), Space: O(1)

Recursive version:

function binarySearchRecursive(nums: number[], target: number, left: number = 0, right: number = nums.length - 1): number {
  if (left > right) return -1;
  
  const mid = Math.floor((left + right) / 2);
  
  if (nums[mid] === target) return mid;
  if (nums[mid] < target) return binarySearchRecursive(nums, target, mid + 1, right);
  return binarySearchRecursive(nums, target, left, mid - 1);
}

Pattern 2: Search Insert Position

Find index where target should be inserted.

function searchInsert(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return left;
}

Time: O(log n), Space: O(1)

Explanation: When loop ends, left points to insertion position.

Pattern 3: Find First and Last Position

Find first and last occurrence of target.

function searchRange(nums: number[], target: number): number[] {
  const first = findFirst(nums, target);
  if (first === -1) return [-1, -1];
  
  const last = findLast(nums, target);
  return [first, last];
}

function findFirst(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
  let result = -1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] === target) {
      result = mid;
      right = mid - 1; // Continue searching left
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return result;
}

function findLast(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
  let result = -1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] === target) {
      result = mid;
      left = mid + 1; // Continue searching right
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return result;
}

Time: O(log n), Space: O(1)

Pattern 4: Search in Rotated Sorted Array

Search target in rotated sorted array (no duplicates).

function searchRotated(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] === target) return mid;
    
    // Left half is sorted
    if (nums[left] <= nums[mid]) {
      if (target >= nums[left] && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      // Right half is sorted
      if (target > nums[mid] && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  
  return -1;
}

Time: O(log n), Space: O(1)

With duplicates:

function searchRotatedWithDuplicates(nums: number[], target: number): boolean {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] === target) return true;
    
    // Handle duplicates
    if (nums[left] === nums[mid] && nums[mid] === nums[right]) {
      left++;
      right--;
      continue;
    }
    
    if (nums[left] <= nums[mid]) {
      if (target >= nums[left] && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      if (target > nums[mid] && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  
  return false;
}

Time: O(n) worst case, O(log n) average, Space: O(1)

Pattern 5: Find Minimum in Rotated Sorted Array

Find minimum element in rotated sorted array.

function findMin(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;
  
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    
    // Right half is sorted, minimum is in left half
    if (nums[mid] < nums[right]) {
      right = mid;
    } else {
      // Left half is sorted, minimum is in right half
      left = mid + 1;
    }
  }
  
  return nums[left];
}

Time: O(log n), Space: O(1)

With duplicates:

function findMinWithDuplicates(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;
  
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] < nums[right]) {
      right = mid;
    } else if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else {
      // Can't decide, shrink right
      right--;
    }
  }
  
  return nums[left];
}

Time: O(n) worst case, O(log n) average, Space: O(1)

Pattern 6: Search in 2D Matrix

Search target in sorted 2D matrix (each row and column sorted).

function searchMatrix(matrix: number[][], target: number): boolean {
  if (matrix.length === 0) return false;
  
  let row = 0;
  let col = matrix[0].length - 1;
  
  while (row < matrix.length && col >= 0) {
    if (matrix[row][col] === target) {
      return true;
    } else if (matrix[row][col] > target) {
      col--;
    } else {
      row++;
    }
  }
  
  return false;
}

Time: O(m + n), Space: O(1)

Fully sorted matrix (binary search):

function searchMatrixSorted(matrix: number[][], target: number): boolean {
  if (matrix.length === 0) return false;
  
  const m = matrix.length;
  const n = matrix[0].length;
  let left = 0;
  let right = m * n - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const row = Math.floor(mid / n);
    const col = mid % n;
    
    if (matrix[row][col] === target) {
      return true;
    } else if (matrix[row][col] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return false;
}

Time: O(log(m * n)), Space: O(1)

Pattern 7: Find Peak Element

Find peak element (greater than neighbors).

function findPeakElement(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;
  
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] > nums[mid + 1]) {
      // Peak is in left half (including mid)
      right = mid;
    } else {
      // Peak is in right half
      left = mid + 1;
    }
  }
  
  return left;
}

Time: O(log n), Space: O(1)

Explanation: Always move toward larger neighbor.

Pattern 8: Find K Closest Elements

Find K closest elements to target.

function findClosestElements(arr: number[], k: number, target: number): number[] {
  let left = 0;
  let right = arr.length - k;
  
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    
    // Compare distances
    if (target - arr[mid] > arr[mid + k] - target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  
  return arr.slice(left, left + k);
}

Time: O(log n), Space: O(k)

Pattern 9: Search in Sorted Array of Unknown Size

Search in array where size is unknown (using reader interface).

interface ArrayReader {
  get(index: number): number;
}

function searchUnknownSize(reader: ArrayReader, target: number): number {
  // Find bounds
  let left = 0;
  let right = 1;
  
  while (reader.get(right) < target) {
    left = right;
    right *= 2;
  }
  
  // Binary search in bounds
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const value = reader.get(mid);
    
    if (value === target) return mid;
    if (value === 2147483647 || value > target) { // 2147483647 = out of bounds
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  
  return -1;
}

Time: O(log n), Space: O(1)

Pattern 10: Find Right Interval

Find rightmost interval for each interval.

function findRightInterval(intervals: number[][]): number[] {
  const n = intervals.length;
  const starts = intervals.map((interval, index) => [interval[0], index]);
  starts.sort((a, b) => a[0] - b[0]);
  
  const result: number[] = [];
  
  for (const interval of intervals) {
    const end = interval[1];
    
    // Binary search for first start >= end
    let left = 0;
    let right = n - 1;
    let found = -1;
    
    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      
      if (starts[mid][0] >= end) {
        found = starts[mid][1];
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    
    result.push(found);
  }
  
  return result;
}

Time: O(n log n), Space: O(n)

Pattern 11: Capacity to Ship Packages

Find minimum capacity to ship packages within D days (binary search on answer).

function shipWithinDays(weights: number[], days: number): number {
  let left = Math.max(...weights);
  let right = weights.reduce((a, b) => a + b, 0);
  
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    
    if (canShip(weights, days, mid)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  
  return left;
}

function canShip(weights: number[], days: number, capacity: number): boolean {
  let currentWeight = 0;
  let daysNeeded = 1;
  
  for (const weight of weights) {
    if (currentWeight + weight > capacity) {
      daysNeeded++;
      currentWeight = weight;
    } else {
      currentWeight += weight;
    }
  }
  
  return daysNeeded <= days;
}

Time: O(n * log(sum)), Space: O(1)

Binary search on answer: Search space is capacity range.

Pattern 12: Split Array Largest Sum

Split array into m subarrays, minimize largest sum.

function splitArray(nums: number[], m: number): number {
  let left = Math.max(...nums);
  let right = nums.reduce((a, b) => a + b, 0);
  
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    
    if (canSplit(nums, m, mid)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  
  return left;
}

function canSplit(nums: number[], m: number, maxSum: number): boolean {
  let currentSum = 0;
  let splits = 1;
  
  for (const num of nums) {
    if (currentSum + num > maxSum) {
      splits++;
      currentSum = num;
    } else {
      currentSum += num;
    }
  }
  
  return splits <= m;
}

Time: O(n * log(sum)), Space: O(1)

When to Use Binary Search

Use binary search when:

  • Array is sorted (or can be sorted)
  • Need O(log n) time complexity
  • Search space can be reduced by half
  • Problem asks for "find minimum/maximum" that satisfies condition
  • Monotonic property exists (if condition works for x, works for all > x)

Key insight: Binary search can be used even when array isn't explicitly sorted, if search space has monotonic property.

Template (Standard Binary Search)

function binarySearchTemplate(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return -1; // or left for insertion position
}

Template (Binary Search on Answer)

function binarySearchOnAnswer(condition: (mid: number) => boolean, left: number, right: number): number {
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    
    if (condition(mid)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  
  return left;
}

Time and Space Complexity Summary

  • Standard binary search: O(log n) time, O(1) space
  • Search in rotated: O(log n) time, O(1) space
  • Search in 2D: O(m + n) or O(log(m * n)) time, O(1) space
  • Binary search on answer: O(n * log(range)) time, O(1) space
  • Find peak: O(log n) time, O(1) space

Practice Tips

  1. Identify sorted property - Is array sorted or can be sorted?
  2. Monotonic property - Does condition have monotonicity?
  3. Boundary conditions - Handle left <= right vs left < right
  4. Duplicates - May need linear scan in worst case
  5. Binary search on answer - When searching for optimal value

Common Mistakes

  1. Off-by-one errors - left <= right vs left < right
  2. Infinite loops - Not updating left/right correctly
  3. Wrong comparison - Comparing wrong values
  4. Not handling duplicates - May need to scan linearly
  5. Integer overflow - Use left + Math.floor((right - left) / 2)

Related Concepts

  • Two Pointers - Alternative for some search problems
  • Sorting - Often prerequisite for binary search
  • Divide and Conquer - Core of binary search
  • Search Space Reduction - Key insight

Search in array is essential for efficient lookups. Master binary search and its variations, and you'll solve many search problems optimally in coding interviews.

← PreviousArray SortingNext →Array Manipulation