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

Question

要解决的问题是:

给定一个长度为N的整数列表，在不执行任何乘法、除法或位移位操作的情况下，确定元素x是否在列表中。在O(log N)时间内完成。

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

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

在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;
}

Answer 3

使用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)