Binary Search:
* main idea is to track the current range of reasonable guesses
* EX: You must guess a number between 1-100, you’ve already guessed 10 and your partner said the number was higher so you can conclude that numbers between 10-100 are the only reasonable guesses, but anything below 10 is an unreasonable guess. Now you’ve guessed the number is 64, and your partner has said the number is lower than that. So you can conclude that a number between 10-64 are the only reasonable guesses.
* To quickly get to the correct number, choose the middle number between both numbers within the reasonable numbers, the middle number of 10-64 can be given by doing (10+64)/2 and the answer is 37. So you guess the number is 37, whether the actual number is greater or less than 37 you’ve halved the size of the range.
\
Step by step description into using binary search to play the guessing game: for the guessing game, keep track of the set of reasonable guesses
1. Let the current minimum reasonable guess be variable min = 1 & the current maximum reasonable guess be variable max = n
2. Guess the average of max & min, if its a decimal round it down to an integer
3. If guessed correctly, then stop.
4. If the guess was too low, set min to be one larger than the guess
5. If the guess was too high, set max to be one smaller than the guess To understand how many steps go into a certain amount of inputs:
6. Find how many bits it takes to represent the input. If there’s 1 input then there’s 1 step because it takes only 1 bit to represent the input.
7. Binary search algorithm grows at a slow rate because of this process
8. for finding an item from a sorted list of items as the data must be sorted (or binary search cant work) and reduces the number of checks by half to search for a desired value.
\*remember: the steps r also binary representations of its corresponding input
Terms matching with Binary Search:
* Logarithmic- procedure used for Binary Search, starts at the middle and removes half of the data, repeating the process until the desired value is found or all elements have been eliminated
* Class birthdays- every student in class lines up, person with a birthday right in the middle of everyones is chosen, eliminate half the data be it the numbers greater or less than that student’s bday, continue the process until the actual date is exacted
* Sorted Data- how data is sorted, not in a definitive way, depends on the problem
\
Efficiency of Binary Search:
* Binary Search is efficient as the number of steps it takes to complete an algorithm vs its matching input is much smaller. Why? The number of bits to represent a number is smaller than the number, and drastically smaller than a large number. EX: It takes three bits to represent 10 but 4 bits to represent 15, comparing both, 4 bits is much less than 3 to its corresponding number.