On python please # Code the function BinarySearch(x, intList) # that returns Tru

Question

On python please

# Code the function BinarySearch(x, intList)
# that returns True if x is in intList, False otherwise,
# where x is an integer, intList is a sorted list of integers
# The function must be recursive running in O( log n ) time
# where n = len(intList)

def BinarySearch(x, intList):
#--- Code ----

#--- until here ---@

intList = [ 3, 10, 11, 15, 23, 25, 38, 45, 49, 69, 81]
xList=[45, 13, 4, 60, 23]
out=[]
for x in xList:
out.append([x, BinarySearch(x, intList)])
print(out)
# This should show
# [[45, True], [13, False], [4, False], [60, False], [23, True]]

Explanation / Answer

# Code the function BinarySearch(x, intList)
#   that returns True if x is in intList, False otherwise,
#   where x is an integer, intList is a sorted list of integers
# The function must be recursive running in O( log n ) time
#   where n = len(intList)

def BinarySearch(x, intList):
    #--- Code ----
    leng = len(intList)
    if leng == 0 :
        return False
    mid = leng/2
    if intList[mid] == x :
        return True
    elif intList[mid] < x :
        return BinarySearch(x, intList[mid+1:leng])
    elif intList[mid] > x :
        return BinarySearch(x, intList[0:mid])
     #--- until here ---@

intList = [ 3, 10, 11, 15, 23, 25, 38, 45, 49, 69, 81]
xList=[45, 13, 4, 60, 23]
out=[]
for x in xList:
    out.append([x, BinarySearch(x, intList)])
print(out)
# This should show
# [[45, True], [13, False], [4, False], [60, False], [23, True]]

Check this out! Happy with the code?

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.