# Iterative Implementation of Binary Search
def binSearchIterative(x,xs):
    left = 0
    right = len(xs) - 1
    while left <= right:
        mid = (left + right) // 2
        if xs[mid] < x:
            # x must be on the right side
            left = mid + 1
        elif xs[mid] == x:
            return True
        else:
            # x must be on the left side
            right = mid - 1
    return False

xs = [10,20,30,40,50,60,70,80,90,100,110,120,130,140,150]
print(binSearchIterative(35,xs))
print(binSearchIterative(50,xs))
xs = []
print(binSearchIterative(35,xs))

False
True
False

# Iterative Implementation of Binary Search
def binSearchIterative2(x,xs):
    num_iterations = 0
    while len(xs) > 0:
        num_iterations = num_iterations + 1
        mid = (0 + len(xs) - 1) // 2
        if xs[mid] < x:
            # x must be on the right side
            xs = xs[mid+1:]
        elif xs[mid] == x:
            return True
        else:
            # x must be on the left side
            xs = xs[0:mid-1]
    print(num_iterations)
    return False

xs = [10,20,30,40,50,60,70,80,90,100,110,120,130,140,150]
print(binSearchIterative2(35,xs))
print(binSearchIterative(50,xs))
xs = []
print(binSearchIterative2(35,xs))

3
False
True
0
False

xs = []
for i in range(1,1001):
    xs.append(10*i)

print(binSearchIterative2(35,xs))

10
False

# Recursive Implementation of Binary Search
def binSearchRecursive(x,xs):
    if len(xs) == 0:
        return False
    mid = (0 + len(xs) - 1) // 2
    if xs[mid] < x:
        # x must be on the right side
        return binSearchRecursive(x,xs[mid+1:])
    elif xs[mid] == x:
        return True
    else:
        # x must be on the left side
        return binSearchRecursive(x,xs[0:mid-1])

xs = [10,20,30,40,50,60,70,80,90,100,110,120,130,140,150]
print(binSearchRecursive(35,xs))
print(binSearchRecursive(50,xs))
xs = []
print(binSearchRecursive(35,xs))

False
True
False

11//2

5

def sequentialSearch(x,xs):
    for num in xs:
        if num == x:
            return True
    return False

xs = [10,20,30,40,50,60,70,80,90,100,110,120,130,140,150]
print(sequentialSearch(35,xs))
print(sequentialSearch(50,xs))
xs = []
print(sequentialSearch(35,xs))

False
True
False