Course outline

01 · Programming Foundations

02 · Arrays & Strings

03 · Linked Lists

04 · Stacks & Queues

05 · Trees

06 · Heaps & Priority Queues

07 · Graph Algorithms

08 · Greedy Algorithms

09 · Backtracking

10 · Dynamic Programming

11 · Advanced Data Structures

12 · Interview Preparation

Stage 1 · Code

Arrays & Strings

Binary Search

Binary search on arrays, answer space, and rotated arrays.

7 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

Basic Binary Search

Binary search — step through the elimination of halves

Binary Search — target: 13

1lo

9mid

19hi

Step 1 / 5 — Search for 13 in [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

Binary search finds target in sorted array in O(log n). Maintain left, right boundaries. Compute mid = left + (right-left)/2 to avoid overflow. Adjust boundaries based on comparison.

Gobinary-search-templates.go

44 linesLn 1, Col 1Go

Standard uses `left <= right` for exact match. Lower/upper bound use `left < right` with `right = len` for insertion points.

Lower/Upper Bound Variants

These variants are powerful for range queries, counting occurrences, and finding boundaries.

Gousing-bounds-for-range-operations.go

13 linesLn 1, Col 1Go

Count = upper - lower. First = lower bound. Last = upper bound - 1. All O(log n).

Binary Search on Answer Space

When the answer is a number with a monotonic property (if x works, all larger/smaller work), binary search the answer space instead of an array.

Gobinary-search-on-answer:-min-max-subarray-sum.go

34 linesLn 1, Col 1Go

Search space is [max element, total sum]. `canSplit` checks if a candidate max sum is feasible. Monotonic: if x works, any larger also works.

Search in Rotated Sorted Array

Array rotated at unknown pivot. One half is always sorted. Determine which half target lies in.

Gosearch-in-rotated-sorted-array.go

27 linesLn 1, Col 1Go

Check which half is sorted (`nums[left] <= nums[mid]`). Then check if target lies in that sorted half. If yes, search there; otherwise search other half.

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.