Logarithmic Time O(log n) — Practice Tasks¶
Table of Contents¶
- Task 1: Basic Binary Search
- Task 2: Count Occurrences
- Task 3: Search in Rotated Sorted Array
- Task 4: Find Square Root (Integer)
- Task 5: Peak Element
- Task 6: BST Insert and Search
- Task 7: Exponentiation by Squaring
- Task 8: Find Minimum in Rotated Sorted Array
- Task 9: Binary Search on Answer — Koko Eating Bananas
- Task 10: Lower Bound and Upper Bound
- Task 11: Search a 2D Sorted Matrix
- Task 12: Find First Bad Version
- Task 13: Power with Modulo
- Task 14: BST Validation
- Task 15: Median of Two Sorted Arrays
- Benchmark: Binary Search vs Linear Search
Task 1: Basic Binary Search¶
Difficulty: Easy
Implement binary search on a sorted array. Return the index of the target or -1 if not found.
Go¶
package main
import "fmt"
func binarySearch(arr []int, target int) int {
left, right := 0, len(arr)-1
for left <= right {
mid := left + (right-left)/2
if arr[mid] == target {
return mid
} else if arr[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
func main() {
arr := []int{1, 3, 5, 7, 9, 11, 13, 15}
fmt.Println(binarySearch(arr, 7)) // 3
fmt.Println(binarySearch(arr, 6)) // -1
}
Java¶
public class Task1 {
public static int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};
System.out.println(binarySearch(arr, 7)); // 3
System.out.println(binarySearch(arr, 6)); // -1
}
}
Python¶
def binary_search(arr: list[int], target: int) -> int:
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9, 11, 13, 15], 7)) # 3
print(binary_search([1, 3, 5, 7, 9, 11, 13, 15], 6)) # -1
Task 2: Count Occurrences¶
Difficulty: Easy-Medium
Given a sorted array with duplicates, count how many times a target appears. Use O(log n) time.
Go¶
func countOccurrences(arr []int, target int) int {
first := lowerBound(arr, target)
if first == len(arr) || arr[first] != target {
return 0
}
last := upperBound(arr, target)
return last - first
}
func lowerBound(arr []int, target int) int {
left, right := 0, len(arr)
for left < right {
mid := left + (right-left)/2
if arr[mid] < target {
left = mid + 1
} else {
right = mid
}
}
return left
}
func upperBound(arr []int, target int) int {
left, right := 0, len(arr)
for left < right {
mid := left + (right-left)/2
if arr[mid] <= target {
left = mid + 1
} else {
right = mid
}
}
return left
}
Java¶
public static int countOccurrences(int[] arr, int target) {
int first = lowerBound(arr, target);
if (first == arr.length || arr[first] != target) return 0;
int last = upperBound(arr, target);
return last - first;
}
static int lowerBound(int[] arr, int target) {
int lo = 0, hi = arr.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
static int upperBound(int[] arr, int target) {
int lo = 0, hi = arr.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] <= target) lo = mid + 1;
else hi = mid;
}
return lo;
}
Python¶
import bisect
def count_occurrences(arr: list[int], target: int) -> int:
left = bisect.bisect_left(arr, target)
right = bisect.bisect_right(arr, target)
return right - left
print(count_occurrences([1, 2, 2, 2, 3, 4], 2)) # 3
print(count_occurrences([1, 2, 2, 2, 3, 4], 5)) # 0
Task 3: Search in Rotated Sorted Array¶
Difficulty: Medium
Search for a target in a sorted array that has been rotated at some pivot.
Go¶
func searchRotated(arr []int, target int) int {
left, right := 0, len(arr)-1
for left <= right {
mid := left + (right-left)/2
if arr[mid] == target {
return mid
}
// Left half is sorted
if arr[left] <= arr[mid] {
if arr[left] <= target && target < arr[mid] {
right = mid - 1
} else {
left = mid + 1
}
} else { // Right half is sorted
if arr[mid] < target && target <= arr[right] {
left = mid + 1
} else {
right = mid - 1
}
}
}
return -1
}
Java¶
public static int searchRotated(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[left] <= arr[mid]) {
if (arr[left] <= target && target < arr[mid]) right = mid - 1;
else left = mid + 1;
} else {
if (arr[mid] < target && target <= arr[right]) left = mid + 1;
else right = mid - 1;
}
}
return -1;
}
Python¶
def search_rotated(arr: list[int], target: int) -> int:
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
if arr[left] <= arr[mid]:
if arr[left] <= target < arr[mid]:
right = mid - 1
else:
left = mid + 1
else:
if arr[mid] < target <= arr[right]:
left = mid + 1
else:
right = mid - 1
return -1
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0)) # 4
Task 4: Find Square Root (Integer)¶
Difficulty: Easy
Compute the integer square root of a non-negative integer using binary search.
Go¶
func intSqrt(n int) int {
if n < 2 {
return n
}
left, right := 1, n/2
for left <= right {
mid := left + (right-left)/2
if mid == n/mid {
return mid
} else if mid < n/mid {
left = mid + 1
} else {
right = mid - 1
}
}
return right
}
Java¶
public static int intSqrt(int n) {
if (n < 2) return n;
int left = 1, right = n / 2;
while (left <= right) {
int mid = left + (right - left) / 2;
long square = (long) mid * mid;
if (square == n) return mid;
else if (square < n) left = mid + 1;
else right = mid - 1;
}
return right;
}
Python¶
def int_sqrt(n: int) -> int:
if n < 2:
return n
left, right = 1, n // 2
while left <= right:
mid = left + (right - left) // 2
if mid * mid == n:
return mid
elif mid * mid < n:
left = mid + 1
else:
right = mid - 1
return right
print(int_sqrt(16)) # 4
print(int_sqrt(17)) # 4
Task 5: Peak Element¶
Difficulty: Medium
Find a peak element in an array where arr[i] != arr[i+1]. A peak is greater than its neighbors.
Go¶
func findPeak(arr []int) int {
left, right := 0, len(arr)-1
for left < right {
mid := left + (right-left)/2
if arr[mid] < arr[mid+1] {
left = mid + 1
} else {
right = mid
}
}
return left
}
Java¶
public static int findPeak(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < arr[mid + 1]) left = mid + 1;
else right = mid;
}
return left;
}
Python¶
def find_peak(arr: list[int]) -> int:
left, right = 0, len(arr) - 1
while left < right:
mid = left + (right - left) // 2
if arr[mid] < arr[mid + 1]:
left = mid + 1
else:
right = mid
return left
print(find_peak([1, 3, 5, 4, 2])) # 2 (value 5)
Task 6: BST Insert and Search¶
Difficulty: Easy
Implement a BST with insert and search operations.
Go¶
type Node struct {
Val int
Left *Node
Right *Node
}
func insert(root *Node, val int) *Node {
if root == nil {
return &Node{Val: val}
}
if val < root.Val {
root.Left = insert(root.Left, val)
} else if val > root.Val {
root.Right = insert(root.Right, val)
}
return root
}
func search(root *Node, val int) bool {
for root != nil {
if val == root.Val {
return true
} else if val < root.Val {
root = root.Left
} else {
root = root.Right
}
}
return false
}
Java¶
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
}
static Node insert(Node root, int val) {
if (root == null) return new Node(val);
if (val < root.val) root.left = insert(root.left, val);
else if (val > root.val) root.right = insert(root.right, val);
return root;
}
static boolean search(Node root, int val) {
while (root != null) {
if (val == root.val) return true;
else if (val < root.val) root = root.left;
else root = root.right;
}
return false;
}
Python¶
class Node:
def __init__(self, val):
self.val = val
self.left = self.right = None
def insert(root, val):
if root is None:
return Node(val)
if val < root.val:
root.left = insert(root.left, val)
elif val > root.val:
root.right = insert(root.right, val)
return root
def search(root, val):
while root:
if val == root.val:
return True
elif val < root.val:
root = root.left
else:
root = root.right
return False
Task 7: Exponentiation by Squaring¶
Difficulty: Easy
Compute base^exp in O(log exp) using iterative squaring.
Go¶
func power(base, exp int) int {
result := 1
for exp > 0 {
if exp%2 == 1 {
result *= base
}
base *= base
exp /= 2
}
return result
}
Java¶
public static long power(long base, int exp) {
long result = 1;
while (exp > 0) {
if (exp % 2 == 1) result *= base;
base *= base;
exp /= 2;
}
return result;
}
Python¶
def power(base: int, exp: int) -> int:
result = 1
while exp > 0:
if exp % 2 == 1:
result *= base
base *= base
exp //= 2
return result
print(power(2, 10)) # 1024
Task 8: Find Minimum in Rotated Sorted Array¶
Difficulty: Medium
Find the minimum element in a rotated sorted array (no duplicates).
Go¶
func findMin(arr []int) int {
left, right := 0, len(arr)-1
for left < right {
mid := left + (right-left)/2
if arr[mid] > arr[right] {
left = mid + 1
} else {
right = mid
}
}
return arr[left]
}
Java¶
public static int findMin(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] > arr[right]) left = mid + 1;
else right = mid;
}
return arr[left];
}
Python¶
def find_min(arr: list[int]) -> int:
left, right = 0, len(arr) - 1
while left < right:
mid = left + (right - left) // 2
if arr[mid] > arr[right]:
left = mid + 1
else:
right = mid
return arr[left]
print(find_min([4, 5, 6, 7, 0, 1, 2])) # 0
Task 9: Binary Search on Answer — Koko Eating Bananas¶
Difficulty: Medium
Koko has n piles of bananas. She can eat at speed k bananas/hour (one pile per hour max). Find the minimum k so she finishes in h hours.
Go¶
import "math"
func minEatingSpeed(piles []int, h int) int {
left, right := 1, 0
for _, p := range piles {
if p > right {
right = p
}
}
for left < right {
mid := left + (right-left)/2
if canFinish(piles, mid, h) {
right = mid
} else {
left = mid + 1
}
}
return left
}
func canFinish(piles []int, speed, h int) bool {
hours := 0
for _, p := range piles {
hours += (p + speed - 1) / speed // ceiling division
}
return hours <= h
}
Java¶
public static int minEatingSpeed(int[] piles, int h) {
int left = 1, right = 0;
for (int p : piles) right = Math.max(right, p);
while (left < right) {
int mid = left + (right - left) / 2;
if (canFinish(piles, mid, h)) right = mid;
else left = mid + 1;
}
return left;
}
static boolean canFinish(int[] piles, int speed, int h) {
int hours = 0;
for (int p : piles) hours += (p + speed - 1) / speed;
return hours <= h;
}
Python¶
import math
def min_eating_speed(piles: list[int], h: int) -> int:
left, right = 1, max(piles)
while left < right:
mid = left + (right - left) // 2
total = sum(math.ceil(p / mid) for p in piles)
if total <= h:
right = mid
else:
left = mid + 1
return left
print(min_eating_speed([3, 6, 7, 11], 8)) # 4
Task 10: Lower Bound and Upper Bound¶
Difficulty: Easy
Implement lower_bound (first index >= target) and upper_bound (first index > target).
Solutions are provided in Task 2 above.
Task 11: Search a 2D Sorted Matrix¶
Difficulty: Medium
Search in a matrix where each row is sorted and the first element of each row is greater than the last element of the previous row. Treat it as a flat sorted array.
Go¶
func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 {
return false
}
rows, cols := len(matrix), len(matrix[0])
left, right := 0, rows*cols-1
for left <= right {
mid := left + (right-left)/2
val := matrix[mid/cols][mid%cols]
if val == target {
return true
} else if val < target {
left = mid + 1
} else {
right = mid - 1
}
}
return false
}
Java¶
public static boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0) return false;
int rows = matrix.length, cols = matrix[0].length;
int left = 0, right = rows * cols - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int val = matrix[mid / cols][mid % cols];
if (val == target) return true;
else if (val < target) left = mid + 1;
else right = mid - 1;
}
return false;
}
Python¶
def search_matrix(matrix: list[list[int]], target: int) -> bool:
if not matrix:
return False
rows, cols = len(matrix), len(matrix[0])
left, right = 0, rows * cols - 1
while left <= right:
mid = left + (right - left) // 2
val = matrix[mid // cols][mid % cols]
if val == target:
return True
elif val < target:
left = mid + 1
else:
right = mid - 1
return False
Task 12: Find First Bad Version¶
Difficulty: Easy
You have n versions [1..n]. Given an API isBad(version) that returns true for bad versions, find the first bad version.
Go¶
func firstBadVersion(n int) int {
left, right := 1, n
for left < right {
mid := left + (right-left)/2
if isBad(mid) {
right = mid
} else {
left = mid + 1
}
}
return left
}
Java¶
public int firstBadVersion(int n) {
int left = 1, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (isBad(mid)) right = mid;
else left = mid + 1;
}
return left;
}
Python¶
def first_bad_version(n: int) -> int:
left, right = 1, n
while left < right:
mid = left + (right - left) // 2
if is_bad(mid):
right = mid
else:
left = mid + 1
return left
Task 13: Power with Modulo¶
Difficulty: Medium
Compute (base^exp) % mod efficiently. Essential for cryptography and competitive programming.
Go¶
func powerMod(base, exp, mod int) int {
result := 1
base %= mod
for exp > 0 {
if exp%2 == 1 {
result = result * base % mod
}
base = base * base % mod
exp /= 2
}
return result
}
Java¶
public static long powerMod(long base, long exp, long mod) {
long result = 1;
base %= mod;
while (exp > 0) {
if (exp % 2 == 1) result = result * base % mod;
base = base * base % mod;
exp /= 2;
}
return result;
}
Python¶
def power_mod(base: int, exp: int, mod: int) -> int:
result = 1
base %= mod
while exp > 0:
if exp % 2 == 1:
result = result * base % mod
base = base * base % mod
exp //= 2
return result
# Python also has built-in: pow(base, exp, mod)
print(power_mod(2, 100, 1000000007))
Task 14: BST Validation¶
Difficulty: Medium
Check whether a binary tree is a valid BST. Use the property that every node's value must be within a valid range.
Go¶
func isValidBST(root *Node) bool {
return validate(root, math.MinInt64, math.MaxInt64)
}
func validate(node *Node, min, max int) bool {
if node == nil {
return true
}
if node.Val <= min || node.Val >= max {
return false
}
return validate(node.Left, min, node.Val) && validate(node.Right, node.Val, max)
}
Java¶
public static boolean isValidBST(Node root) {
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
static boolean validate(Node node, long min, long max) {
if (node == null) return true;
if (node.val <= min || node.val >= max) return false;
return validate(node.left, min, node.val)
&& validate(node.right, node.val, max);
}
Python¶
def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')):
if root is None:
return True
if root.val <= min_val or root.val >= max_val:
return False
return (is_valid_bst(root.left, min_val, root.val) and
is_valid_bst(root.right, root.val, max_val))
Task 15: Median of Two Sorted Arrays¶
Difficulty: Hard
Find the median of two sorted arrays in O(log(min(m, n))) time.
Python (compact solution)¶
def find_median(nums1: list[int], nums2: list[int]) -> float:
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
left, right = 0, m
half = (m + n + 1) // 2
while left <= right:
i = left + (right - left) // 2
j = half - i
left1 = nums1[i - 1] if i > 0 else float('-inf')
right1 = nums1[i] if i < m else float('inf')
left2 = nums2[j - 1] if j > 0 else float('-inf')
right2 = nums2[j] if j < n else float('inf')
if left1 <= right2 and left2 <= right1:
if (m + n) % 2 == 1:
return max(left1, left2)
return (max(left1, left2) + min(right1, right2)) / 2.0
elif left1 > right2:
right = i - 1
else:
left = i + 1
return 0.0
print(find_median([1, 3], [2])) # 2.0
print(find_median([1, 2], [3, 4])) # 2.5
Benchmark: Binary Search vs Linear Search¶
Python Benchmark¶
import time
import random
import bisect
def linear_search(arr, target):
for i, v in enumerate(arr):
if v == target:
return i
return -1
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
sizes = [1_000, 10_000, 100_000, 1_000_000, 10_000_000]
print(f"{'Size':>12} {'Linear (ms)':>12} {'Binary (ms)':>12} {'Bisect (ms)':>12} {'Speedup':>10}")
print("-" * 62)
for n in sizes:
arr = list(range(n))
targets = [random.randint(0, n - 1) for _ in range(1000)]
# Linear search
start = time.perf_counter()
for t in targets:
linear_search(arr, t)
linear_time = (time.perf_counter() - start) * 1000
# Binary search
start = time.perf_counter()
for t in targets:
binary_search(arr, t)
binary_time = (time.perf_counter() - start) * 1000
# bisect (C implementation)
start = time.perf_counter()
for t in targets:
bisect.bisect_left(arr, t)
bisect_time = (time.perf_counter() - start) * 1000
speedup = linear_time / binary_time if binary_time > 0 else float('inf')
print(f"{n:>12,} {linear_time:>12.2f} {binary_time:>12.2f} {bisect_time:>12.2f} {speedup:>10.1f}x")
Expected Output¶
Size Linear (ms) Binary (ms) Bisect (ms) Speedup
--------------------------------------------------------------
1,000 2.50 0.45 0.08 5.6x
10,000 24.00 0.55 0.09 43.6x
100,000 240.00 0.65 0.10 369.2x
1,000,000 2400.00 0.75 0.11 3,200.0x
10,000,000 24000.00 0.85 0.12 28,235.3x
The benchmark clearly shows that binary search (O(log n)) scales dramatically better than linear search (O(n)). The C-implemented bisect module is even faster due to lower constant factors.