CS 0401 Lecture 11: 2.9.17 Binomial Theorem and Lab 4 Overview
Document Summary
Make the guess for the index by guessing the middle. (lo+hi)/2. Return that the guess was either right, too low, or too high. If arr[ mid ] < key // too low: lo = mid +1; If arr[ mid ] > key // too high: hi = mid-1, the lower bound moves up to mid+1 get rid of everything lower than that that we know is not the number. Each time we guess, we are cutting the search space by half. Log2 (x) - 2 to what power will give you the total number in the array: that exponent will be the minimum number of guesses to get the right answer. While lo <= hi: we must test for the equal case because they need to not cross. Brute force/linear/sequential: incurs a complexity of n on the array of n: complexity is in efficient omega on the order of n directly proportional to n double n, double the run time.