给定长度为 N 的有序整数列表，确定元素 x 是否在列表中

Question

要解决的问题是：

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.

我已经使用修改后的二进制搜索解决了这个问题，但我不确定这是否满足所需的时间复杂度。有更好的解决方案吗？

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

Answer 1

如果x的索引存在，我们可以通过逐位构造索引找到它：

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

那么我们需要做的就是：

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

Answer 2

使用 log2(N) 调用仅通过加法而不使用循环来查找：

def find_pos(step, arr, val):
    next = step+step
    if next < len(arr):
       choose = find_pos(next, arr, val)
    else:
       choose = step
    next = choose + step
    if next < len(arr) and arr[next] <= val:
        return next
    if arr[choose] <= val:
        return choose
    return 0

def find_val(arr, val):
    index = find_pos(1, arr, val)
    if arr[index] == val:
        print "found %d at %d" % (val, index)
    else:
        print "%d not found" % (val)

Answer 3

O(logN)时间完成，必须使用二分查找。因此，这里的关键点是找到一种无需乘法、除法和位移位即可除以 2 的方法。这是一个在恒定时间内执行的函数：

int divideTwo(int x) {
    vector<int> bit = {
        0x1, 0x2, 0x4, 0x8,
        0x10, 0x20, 0x40, 0x80,
        0x100, 0x200, 0x400, 0x800,
        0x1000, 0x2000, 0x4000, 0x8000,
        0x10000, 0x20000, 0x40000, 0x80000,
        0x100000, 0x200000, 0x400000, 0x800000,
        0x1000000, 0x2000000, 0x4000000, 0x8000000,
        0x10000000, 0x20000000, 0x40000000, 0
    };

    int v = 0;
    for (int i = 1; i < bit.size() - 1 && x > 0; ++i) {
        if ((x & bit[i]) > 0)
        {
            v += bit[i - 1];
            x -= bit[i];
        }
    }
    return v;
}

给定长度为 N 的有序整数列表，确定元素 x 是否在列表中

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

python

algorithm

binary-search

sortedlist

data-structures