Given a sorted list of integers of length N, determine if an element x is in the list

The problem to solve is:

Given a sorted list of integers of length N, determine if an element x is in the list without performing any multiplication, division, or bit-shift operations. Do this in O(log N) time.

I have solved this problem using a modified binary search, but I'm not sure if this satisfies the time complexity required. Is there a better solution?

def get_mid(start, end):
    mid = start + 1
    sum_ = start + end
    prev = mid
    while mid < end and (mid + mid) != sum_ and (mid + mid + 1) != sum_:
        prev = mid
        mid += mid
    if mid > end:
        return prev
    return mid



def bin_search(arr, x):
    start, end = 0, len(arr) - 1

    while start <= end:
        mid = get_mid(start, end)
        if mid == 1:
            return x in arr[:end]
        if x > arr[mid]:
            start = mid + 1
        elif x < arr[mid]:
            end = mid - 1
        else:
            return True

    return False

Solution 1:

We can find the index of x if it exists by constructing the index bit-by-bit:

def find_idx_sorted(arr, x):
    powers_of_two = [1]
    while powers_of_two[-1] < len(arr):
        powers_of_two.append(powers_of_two[-1] + powers_of_two[-1])

    idx = 0
    for pot in reversed(powers_of_two):
        if idx + pot < len(arr) and x >= arr[idx + pot]:
           idx += pot
    
    return idx

Then all we need to do:

def contains_sorted(arr, x):
    return arr[find_idx_sorted(arr, x)] == x