Interview Gym PRO

Binary Search

Guess a number from 1–100: ask "higher or lower?" and you need at most 7 guesses. Whenever you can answer a yes/no question that cuts the possibilities in half, you can solve in O(log n). It also works on answers, not only arrays.

After this topic: You can write a bug-free binary search, adapt it to rotated arrays, and search over the answer itself.

Do these first: Two Pointers

0 of 7 solved0%

Step 1 · Read the lesson

Halve the search space whenever a yes/no condition is monotonic.

Step 2 · Solve the problems in order

Try each one for about 20 minutes first. Problems with a Run code tab are checked right here. If you are stuck, open Nudge, think again, then Idea. Go skeleton only gives the function shape, and Reference solution is for comparing after you have tried. Tick the box when you could solve it again without help.

1.Binary Search Easy
Look at the middle element. What does it tell you about which half to keep?
lo=0, hi=n−1; mid; if equal return, if too small lo=mid+1, else hi=mid−1.
Target: O(log n) time, O(1) space
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func search(nums []int, target int) int
Tested with go test. Try it yourself first, then compare. It is explained step by step on the Binary Search lesson page.
// Search (LeetCode 704): index of target in a sorted slice, or -1. // Find the first index whose value is >= target, then check it really is target. func Search(nums []int, target int) int { lo, hi := 0, len(nums) for lo < hi { mid := lo + (hi-lo)/2 if nums[mid] >= target { hi = mid } else { lo = mid + 1 } } if lo < len(nums) && nums[lo] == target { return lo } return -1 }

2.Search a 2D Matrix Medium

Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.

func searchMatrix(matrix [][]int, target int) bool

Tested with go test. Try it yourself first, then compare.

// SearchMatrix: rows are sorted and each row starts after the previous one ends, so the matrix is one sorted
// array in disguise. Index mid maps to row mid/cols and column mid%cols.
func SearchMatrix(matrix [][]int, target int) bool {
	rows, cols := len(matrix), len(matrix[0])
	lo, hi := 0, rows*cols-1
	for lo <= hi {
		mid := lo + (hi-lo)/2
		v := matrix[mid/cols][mid%cols]
		switch {
		case v == target:
			return true
		case v < target:
			lo = mid + 1
		default:
			hi = mid - 1
		}
	}
	return false
}

3.Koko Eating Bananas Medium

Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.

func minEatingSpeed(piles []int, h int) int

Tested with go test. Try it yourself first, then compare. It is explained step by step on the Binary Search lesson page.

// MinEatingSpeed (LeetCode 875): smallest speed k so every pile is eaten within h hours.
// Search the ANSWER space [1, max(piles)]: "can finish at speed k" is false..false,true..true.
func MinEatingSpeed(piles []int, h int) int {
	maxPile := 0
	for _, p := range piles {
		maxPile = max(maxPile, p)
	}
	// candidate speed for index i is i+1
	i := firstTrue(maxPile, func(i int) bool {
		k, hours := i+1, 0
		for _, p := range piles {
			hours += (p + k - 1) / k // ceil(p / k)
		}
		return hours <= h
	})
	return i + 1
}

4.Find Minimum in Rotated Sorted Array Medium

Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.

func findMin(nums []int) int

Tested with go test. Try it yourself first, then compare. It is explained step by step on the Binary Search lesson page.

// SearchRotated (LeetCode 33): target in a rotated sorted slice of distinct values, or -1.
// Step 1: find the rotation point (index of the minimum). Step 2: binary search the right half.
func SearchRotated(nums []int, target int) int {
	n := len(nums)
	if n == 0 {
		return -1
	}
	// the minimum is the first element that is <= the last element
	pivot := firstTrue(n, func(i int) bool { return nums[i] <= nums[n-1] })
	// treat the slice as sorted with a shifted index: real = (i + pivot) % n
	i := firstTrue(n, func(i int) bool { return nums[(i+pivot)%n] >= target })
	if i < n && nums[(i+pivot)%n] == target {
		return (i + pivot) % n
	}
	return -1
}

// FindMin (LeetCode 153): minimum of a rotated sorted slice of distinct values.
func FindMin(nums []int) int {
	n := len(nums)
	return nums[firstTrue(n, func(i int) bool { return nums[i] <= nums[n-1] })]
}

5.Search in Rotated Sorted Array Medium

Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.

func search(nums []int, target int) int

Tested with go test. Try it yourself first, then compare. It is explained step by step on the Binary Search lesson page.

// SearchRotated (LeetCode 33): target in a rotated sorted slice of distinct values, or -1.
// Step 1: find the rotation point (index of the minimum). Step 2: binary search the right half.
func SearchRotated(nums []int, target int) int {
	n := len(nums)
	if n == 0 {
		return -1
	}
	// the minimum is the first element that is <= the last element
	pivot := firstTrue(n, func(i int) bool { return nums[i] <= nums[n-1] })
	// treat the slice as sorted with a shifted index: real = (i + pivot) % n
	i := firstTrue(n, func(i int) bool { return nums[(i+pivot)%n] >= target })
	if i < n && nums[(i+pivot)%n] == target {
		return (i + pivot) % n
	}
	return -1
}

// FindMin (LeetCode 153): minimum of a rotated sorted slice of distinct values.
func FindMin(nums []int) int {
	n := len(nums)
	return nums[firstTrue(n, func(i int) bool { return nums[i] <= nums[n-1] })]
}

6.Time Based Key-Value Store Medium

Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.

type TimeMap struct{}
func Constructor() TimeMap
func (t *TimeMap) Set(key string, value string, timestamp int)
func (t *TimeMap) Get(key string, timestamp int) string

Tested with go test. Try it yourself first, then compare.

// TimeMap keeps every (timestamp, value) for a key in insertion order. Timestamps only increase,
// so each list is already sorted and Get can binary-search it.
type TimeMap struct{ data map[string][]entry }
type entry struct {
	ts    int
	value string
}

func NewTimeMap() *TimeMap { return &TimeMap{data: map[string][]entry{}} }

func (t *TimeMap) Set(key, value string, ts int) {
	t.data[key] = append(t.data[key], entry{ts, value})
}

// Get returns the value with the largest timestamp <= ts, or "".
func (t *TimeMap) Get(key string, ts int) string {
	list := t.data[key]
	i := sort.Search(len(list), func(i int) bool { return list[i].ts > ts }) // first entry that is too new
	if i == 0 {
		return ""
	}
	return list[i-1].value
}

7.Median of Two Sorted Arrays Hard

Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.

func findMedianSortedArrays(nums1 []int, nums2 []int) float64

Tested with go test. Try it yourself first, then compare.

// FindMedianSortedArrays: binary-search how many elements the SHORTER array puts in the left half.
// A split is correct when everything on the left is <= everything on the right.
func FindMedianSortedArrays(a, b []int) float64 {
	if len(a) > len(b) {
		a, b = b, a
	}
	const inf = 1 << 60
	half := (len(a) + len(b) + 1) / 2
	lo, hi := 0, len(a)
	for lo <= hi {
		i := (lo + hi) / 2 // elements taken from a
		j := half - i      // elements taken from b
		aLeft, aRight, bLeft, bRight := -inf, inf, -inf, inf
		if i > 0 {
			aLeft = a[i-1]
		}
		if i < len(a) {
			aRight = a[i]
		}
		if j > 0 {
			bLeft = b[j-1]
		}
		if j < len(b) {
			bRight = b[j]
		}
		switch {
		case aLeft > bRight:
			hi = i - 1 // took too many from a
		case bLeft > aRight:
			lo = i + 1 // took too few from a
		default:
			leftMax := max(aLeft, bLeft)
			if (len(a)+len(b))%2 == 1 {
				return float64(leftMax)
			}
			return float64(leftMax+min(aRight, bRight)) / 2
		}
	}
	return 0
}

Step 3 · What this unlocks

Trees