Frontend School
DashboardProblemsLearnPracticeMock InterviewReportsStatsBuy Credits
DashboardProblemsLearnPracticeMock Interview
DSA for Frontend Engineers
  1. 1.Introduction to DSA for Frontend Engineers
  2. 2.JavaScript Fundamentals for DSA
  3. 3.Arrays and Strings: Core Techniques
  4. 4.Objects and Hash Maps in JavaScript
  5. 5.Linked Lists: Building Blocks
  6. 6.Stacks and Queues: LIFO & FIFO
  7. 7.Recursion and Iteration: Problem Solving Paradigms
  8. 8.Introduction to Trees: Binary Trees & BSTs
  9. 9.Tree Traversal Algorithms (BFS & DFS)
  10. 10.Sorting Algorithms I: Basics
  11. 11.Sorting Algorithms II: Divide & Conquer
  12. 12.Searching Algorithms: Linear & Binary Search
  13. 13.Graphs: Representation & Traversals
  14. 14.Dynamic Programming I: Memoization
  15. 15.Heaps and Priority Queues
  16. 16.Tries (Prefix Trees) for Autocomplete & Search
  17. 17.Advanced Graph Algorithms: Shortest Paths & MST
  18. 18.Dynamic Programming II: Tabulation & Frontend Patterns
  19. 19.Frontend System Design with DSA Lens
  20. 20.Interview Strategies & Advanced Problem Solving
DSA for Frontend Engineers
12

DSA · Lesson 12 of 20 · 4 min

Searching Algorithms: Linear & Binary Search

This topic is your first filter for "Is the data sorted?"—the single most important question for search-related problems.

Linear Search: The O(n) Baseline

Linear search is your default for unsorted data. You check every item, one by one. It's simple, requires no setup, and is the only option if the collection has no order.

In an interview, you mention linear search to establish a baseline. It's the brute-force O(n) solution. If the data is small or you only need to search once, it can be the practical choice. But you should immediately pivot to a better approach if the constraints allow.

Its time complexity is O(n) and its space complexity is O(1). There's not much more to it.

The Key Question: "Is the data sorted?"

This is the question you must ask before writing any search code. The answer determines your entire strategy.

If the answer is "yes," you can use binary search for an O(log n) lookup. This is a massive performance win on large arrays. An array of 1 million items takes at most 20 comparisons with binary search, versus a million with linear.

If the answer is "no," follow up: "Will I need to perform many searches on this data?"

  • One search: Just use linear search. O(n) is better than the O(n log n) cost of sorting plus the O(log n) search.
  • Many searches: The cost of sorting upfront (O(n log n)) is likely worth it. After that, every subsequent search is a cheap O(log n). This trade-off is a critical point to discuss.

The trap: Don't just start sorting. Justify the O(n log n) cost. Explain that you're "amortizing" the cost of the sort over many fast lookups. This shows you're thinking about the entire lifecycle of the data, not just a single function call.

How to Implement Binary Search Correctly

Binary search works by repeatedly halving the search space. You maintain a left and right pointer defining your search window. You check the middle, and based on the comparison, you discard the half where the target cannot be.

The iterative approach is standard. It's more performant and avoids stack overflow risk compared to recursion.

function binarySearch(arr: number[], target: number): number {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        // This mid calculation prevents overflow in other languages.
        // It's good practice, even if not a risk in JS with its number type.
        const mid = left + Math.floor((right - left) / 2);

        if (arr[mid] === target) {
            return mid;
        }

        if (arr[mid] < target) {
            // Target is in the right half, discard the left.
            left = mid + 1;
        } else {
            // Target is in the left half, discard the right.
            right = mid - 1;
        }
    }

    // Target was not found.
    return -1;
}

The trap: Off-by-one errors will kill your implementation.

  1. Loop Condition: Use while (left <= right). If you use left < right, the loop will exit when left and right point to the same element, and you'll fail to check the last possible candidate.
  2. Pointer Updates: Always move the pointers past the middle element using mid + 1 and mid - 1. If you use left = mid or right = mid, you risk an infinite loop when the search space narrows to two elements.

This flow shows how the window [left...right] shrinks with each step.

Applying Binary Search to Harder Problems

Interviewers won't just ask you to implement a standard binary search. They will test if you can adapt the core concept. The search space doesn't have to be a simple array; it can be a range of numbers, versions, or any other ordered set.

A classic example is Search in Rotated Sorted Array. The array is sorted but "pivoted," like [4, 5, 6, 7, 0, 1, 2].

A naive solution is a linear scan (O(n)). The optimal O(log n) solution is a modified binary search. In each step, you determine which half of the current window ([left...mid] or [mid...right]) is still sorted. Then, you check if your target lies within that sorted portion. If it does, you search there; otherwise, you search the other, non-sorted portion.

Understanding this pattern—finding a sorted subspace and narrowing your search—is the key to solving a whole class of "hard" search problems.

Try it

Implement a function findFirstOccurrence(arr: number[], target: number): number on a sorted array that may contain duplicates. Standard binary search finds any occurrence. Modify it to find the first one. Hint: when you find the target at mid, don't return immediately. Record the index and try to find an earlier one by continuing your search in the left half.

Next: Now that we can find things, let's look at how data is connected in Graphs: Representation & Traversals.

Lock it in — apply this lesson under interview conditions.

Try a free mock interviewPractice this pattern
Previous

Sorting Algorithms II: Divide & Conquer

Next

Graphs: Representation & Traversals