itera?on = n, n/2, n/4, ... 1 • Hence the number of itera?ons = O( log n ) • Therefore number of comparisons = O(log n) Lipyeow Lim -‐-‐ University of Hawaii at Manoa 11 (lo, hi) = (0,n-1) mid = lo + (hi-lo)/2 While(hi>lo && E[mid].age!=30) { if (E[mid].age < 30) { lo=mid } else { hi=mid } mid = lo + (hi-lo)/2 } Output all satisfying tuples around E[mid] 16, 19, 19, 20, 26, 30, 30, 31, 36 16, 19, 19, 20, 26, 30, 30, 31, 36 2 cmp 2 cmp 16, 19, 19, 20, 30, 31, 31, 31, 36 16, 19, 19, 20, 30, 31, 31, 31, 36 What is the worse case?