All Roadmaps›🧠 Data Structures & Algorithms›Phase 2›Searching Algorithms (Linear & Binary Search)

Searching Algorithms (Linear & Binary Search)

0/14 in this phase0/57 across the roadmap

📖 Concept

Searching is the other fundamental algorithm category. The leap from O(n) linear search to O(log n) binary search is one of the most important optimizations in computing.

Linear Search — O(n):

  • Check each element one by one
  • Works on unsorted data
  • Best for small arrays or one-time searches

Binary Search — O(log n):

  • Requires sorted data
  • Halves search space each step
  • log₂(1,000,000) ≈ 20 — only 20 comparisons for a million elements!

Binary search template (the bug-free version):

lo = 0, hi = n - 1
while (lo <= hi):
    mid = lo + (hi - lo) / 2
    if found: return mid
    if target > mid: lo = mid + 1
    else: hi = mid - 1

Binary search variants:

  1. Find exact value
  2. Find first occurrence (leftmost)
  3. Find last occurrence (rightmost)
  4. Find insertion point (lower bound / upper bound)
  5. Search on answer (binary search on the answer space)

🏠 Real-world analogy: Linear search is reading a phone book one name at a time. Binary search is opening to the middle, deciding if your name is before or after, then doing the same on the half — like how you actually use a dictionary.

💻 Code Example

codeTap to expand ⛶
1// LINEAR SEARCH — O(n)
2function linearSearch(arr: number[], target: number): number {
3  for (let i = 0; i < arr.length; i++) {
4    if (arr[i] === target) return i;
5  }
6  return -1;
7}
8

9// BINARY SEARCH — O(log n), standard template
10function binarySearch(arr: number[], target: number): number {
11  let lo = 0, hi = arr.length - 1;
12  while (lo <= hi) {
13    const mid = lo + Math.floor((hi - lo) / 2);
14    if (arr[mid] === target) return mid;
15    if (arr[mid] < target) lo = mid + 1;
16    else hi = mid - 1;
17  }
18  return -1;
19}
20

21// FIND FIRST OCCURRENCE (leftmost)
22function findFirst(arr: number[], target: number): number {
23  let lo = 0, hi = arr.length - 1, result = -1;
24  while (lo <= hi) {
25    const mid = lo + Math.floor((hi - lo) / 2);
26    if (arr[mid] === target) {
27      result = mid;    // Found, but keep searching left
28      hi = mid - 1;
29    } else if (arr[mid] < target) lo = mid + 1;
30    else hi = mid - 1;
31  }
32  return result;
33}
34

35// FIND LAST OCCURRENCE (rightmost)
36function findLast(arr: number[], target: number): number {
37  let lo = 0, hi = arr.length - 1, result = -1;
38  while (lo <= hi) {
39    const mid = lo + Math.floor((hi - lo) / 2);
40    if (arr[mid] === target) {
41      result = mid;    // Found, but keep searching right
42      lo = mid + 1;
43    } else if (arr[mid] < target) lo = mid + 1;
44    else hi = mid - 1;
45  }
46  return result;
47}
48

49// SEARCH IN ROTATED SORTED ARRAY
50function searchRotated(nums: number[], target: number): number {
51  let lo = 0, hi = nums.length - 1;
52  while (lo <= hi) {
53    const mid = lo + Math.floor((hi - lo) / 2);
54    if (nums[mid] === target) return mid;
55

56    if (nums[lo] <= nums[mid]) { // Left half is sorted
57      if (target >= nums[lo] && target < nums[mid]) hi = mid - 1;
58      else lo = mid + 1;
59    } else { // Right half is sorted
60      if (target > nums[mid] && target <= nums[hi]) lo = mid + 1;
61      else hi = mid - 1;
62    }
63  }
64  return -1;
65}
66

67// BINARY SEARCH ON ANSWER — "Find minimum X such that condition is true"
68// Example: minimum capacity to ship packages in D days
69function shipWithinDays(weights: number[], days: number): number {
70  let lo = Math.max(...weights);
71  let hi = weights.reduce((a, b) => a + b, 0);
72

73  while (lo < hi) {
74    const mid = lo + Math.floor((hi - lo) / 2);
75    if (canShip(weights, days, mid)) hi = mid;
76    else lo = mid + 1;
77  }
78  return lo;
79}
80

81function canShip(weights: number[], days: number, capacity: number): boolean {
82  let daysNeeded = 1, currentLoad = 0;
83  for (const w of weights) {
84    if (currentLoad + w > capacity) {
85      daysNeeded++;
86      currentLoad = 0;
87    }
88    currentLoad += w;
89  }
90  return daysNeeded <= days;
91}

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

  1. Implement binary search (iterative and recursive)
  2. Find the first and last position of a target in a sorted array
  3. Search in a rotated sorted array
  4. Find the square root of a number using binary search (integer)
  5. Find peak element in an array (element greater than neighbors)
  6. Find minimum in a rotated sorted array
  7. Search a 2D sorted matrix using binary search
  8. Koko eating bananas — binary search on answer
  9. Split array largest sum — binary search on answer
  10. Median of two sorted arrays — O(log(min(m,n)))

⚠️ Common Mistakes

  • Off-by-one errors: using lo < hi when you need lo <= hi (or vice versa)

  • Integer overflow in (lo + hi) / 2 — use lo + (hi - lo) / 2 instead

  • Applying binary search to unsorted data — it REQUIRES sorted input (or a monotonic condition)

  • Not handling duplicates properly — standard binary search finds ANY occurrence, not first/last

  • Forgetting the 'binary search on answer' pattern — many optimization problems use it

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Searching Algorithms (Linear & Binary Search)

← PreviousSorting Algorithms (Bubble, Selection, Insertion, Merge, Quick)Next →Two Pointers Pattern