Unit 3.9 + 3.11 Homework
Introduction to the binary search algorithm, it's uses, advantages, and disadvantages
Notes:
Binary search:
- One of the two searches that can be used
- Can only be used with sorted arrays
- Can be used in a while loop or recursive function
- Uses a min/max value, halves it, and tests to see if the selected half value matches a requirement; if it doesn't, it takes either a higher or lower value (whichever is closer) to retest
Sequential search:
- Usually slower than a Binary Search, as it goes through every element in a list
- Can be used in a while loop or recursive function
- Should not be used for long calculations unless you want to explode your computer
Challenges and Homework
You have one homework problem.
Yes just one.
Don't get excited though.
Problem: Given a specific integer N, return the square root of N (R) if N is a perfect square, otherwise, return the square root of N rounded down to the nearest integer
Input: N (Integer)
Output: R (Integer)
Constraints: Do not use any built-in math operations such as sqrt(x) or x**(0.5), Try complete the problem in logarithmic time.
Hint 1: Maybe you can use Binary Search to try and reduce the number of checks you have to perform?
Hint 2: Is there a mathematical pattern amongst numbers and their square roots that could help you reduce the number of searches or iterations you must execute? Is there some value or rule you can set before applying binary search to narrow the range of possible values?
Run the very last code segment below to load test cases and submission function
def binarySearch(N):
low = 0
high = N
while high >= low:
mid = (high + low) // 2
if mid * mid == N:
return mid
elif mid * mid > N:
high = mid - 1
else:
low = mid + 1
return 0
from math import sqrt as sq
test_cases = [0,1,4,85248289,22297284,18939904,91107025,69122596,9721924,37810201,1893294144,8722812816,644398225]
answers = [int(sq(x)) for x in test_cases]
def checkValid():0000000
for i in range(len(test_cases)):
if binarySearch(test_cases[i]) == answers[i]:
print("Check number {} passed".format(i+1))
else:
print("Check number {} failed".format(i+1))
checkValid()
# ignore def sqrt(N), this was just testing one method of finding the square root
def sqrtTest(N):
if (N % 2) == 0:
index = 2
else:
index = 1
divV = index
result = 0
while (result != divV):
result = N / divV
if (divV == result):
return result
divV = divV + index
return 0
r = sqrtTest(100)
print( (r),"(Ignore this, it's just the test method code that runs slower than my PC trying to open Genshin Impact :) )")
def binsearchsqrt(N):
if (N % 2) == 0:
index = 2
else:
index = 1
divV = index
result = 0
while (result != divV):
result = N / divV
if (divV == result):
return result
divV = divV + index
return 0
from math import sqrt as sq
test_cases = [0,1,4,85248289,22297284,18939904,91107025,69122596,9721924,37810201,1893294144,8722812816,644398225]
answers = [int(sq(x)) for x in test_cases]
def checkValid():0000000
for i in range(len(test_cases)):
if binarySearch(test_cases[i]) == answers[i]:
print("Check number {} passed".format(i+1))
else:
print("Check number {} failed".format(i+1))
checkValid()
def calculateNumber(num):
result = num
if (num == 0):
return []
result_list = [result]
while result != 1:
if (result % 2 == 0): # use mod = remander = 0 -> even. 1 = odd
result = result / 2
else:
result = result * 3 + 1
result_list.append(int(result)) # appends the result to a string of results so it can be printed later
return result_list
# Input function
s = ""
while (s != "q"):
print("\nEnter a number or type 'q' to quit.")
s = input()
try:
if s != "q":
num = (int(s))
resultFinal = calculateNumber(num)
print(resultFinal)
except ValueError:
print ("Invalid input.")
