CS 0401 Lecture 11: 2.9.17 Binomial Theorem and Lab 4 Overview

82 views2 pages
School
Course
Professor

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.

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers

Related Documents