Binary search o 1. Divide: Check middle element a 2. Conquer: Recursively search I subarray 口3. Combine: Trivial Example: Find 9 357891215
Binary search 1. Divide: Check middle element. 2. Conquer: Recursively search 1 subarray. 3. Combine: Trivial. Example: Find 9 3 5 7 8 9 12 15
Recurrence for binary search 7mn)=(17(mn/2)+e(1) subproblem work dividing number subproblem ana combining size
Recurrence for binary search T( n) = 1 T( n/2) + Θ(1) subproblem number subproblem size work dividing and combining
Recurrence for binary search 7mn)=(17(mn/2)+e(1) subproblem work dividing number subproblem ana combining size a=1.b=2→n0g6=n0 CASE2:f(m)=⊙() T(n)=o(gn)
Recurrence for binary search T( n) = 1 T( n/2) + Θ(1) subproblem number subproblem size work dividing and combining a = 1, b = 2 ⇒ log 0 1 b a n n = = CASE 2: f n( ) (1) = Θ ∴Tn l n () (g ) = Θ