CMPUT101 Lecture Notes - Lecture 23: Binary Search Algorithm, Sorting, Bubble Sort

• School: University of Alberta
• Department: Computing Science
• Course: CMPUT101
• Professor: Marianne Kerolus

Document Summary

While loops create never ending infinity unless there is something to stop it. ^^ eloquent code and if/else statement in one line. Version 2 of the guessing game: we know the number. Then half of 50-100 or 1-50, then half of that half until the correct answer is chosen. Sequential search takes forever on average 50 guesses. Computer will guess a number = (low + high)/2. Read response from user: too low , correct , or too high . If correct, check if user wants to play again. If too low, new guess = (guess+1 + high)/2. If too high, new guess = (low + guess-1)/2. Find 55 in the list or return -1 if not found. Mid (0+9)//2 = 4 > 25 (5+9)//2 = 7 >50 (7+9)//2 = 8 > 66 (7+8+)// = 7 > 50. Find 12 in list or return -1 is not found.