随机查找（一切看命）
对于一个给定的数组，若要查找当中是否包含某个值，传统的方法是遍历数组中的每一个元素，如果找到则返回。如果学习过数据结构，也可以立马想到用哈希表来存储，哈希表的查找性能优异，一般可以达到O(1)的时间复杂度，在最坏情况下也有可能达到O(n)的复杂度。但是今天，我将带来一种有意思的查找方式，也就是通过随机数来对数组进行划分。这种方式运用到了分治的思想，每次随机生成一个下标，然后判断该下标的元素是否等于目标值，如果不等于，则对该下标两边的元素进行递归查找，之后每一次划分的下标也是基于随机数生成。说起来比较抽象，我们来看看代码。
bool RandomFind(const std::vector<int>& v, int l, int r, const int& value) {
if (l > r)
return false;
if (l == r) {
if (v[l] == value)
return true;
return false;
}
std::uniform_int_distribution dis(l, r);
int RandomIndex = dis(g);
bool LeftPart = RandomFind(v, 0, RandomIndex, value);
bool RightPart = RandomFind(v, RandomIndex + 1, r, value);
return LeftPart || RightPart;
}注意递归的终止条件，需要防止数组最小下标l大于最大的下标，还要注意处理好数组只剩下一个元素的情况。由于我们只需要判断是否找到某个元素，因此LeftPart和RightPart只需要有其中一部分找到即可。不过我们还可以对上述代码进行一定的“剪枝”优化，换句话说就是如果随机生成的下标对应的元素是目标值，我们直接return，没必要再做无意义的搜索了。对上面代码稍作改动即可。
bool RandomFind(const std::vector<int>& v, int l, int r, const int& value) {
if (l > r)
return false;
if (l == r) {
if (v[l] == value)
return true;
return false;
}
std::uniform_int_distribution dis(l, r);
int RandomIndex = dis(g);
if (v[RandomIndex] == value)
return true;
bool LeftPart = RandomFind(v, 0, RandomIndex - 1, value);
bool RightPart = RandomFind(v, RandomIndex + 1, r, value);
return LeftPart || RightPart;
}贴个Python版的。
import random
def randomFind(v: list, l: int, r: int, target: int) -> bool:
if l > r:
return False
if l == r:
if v[l] == target:
return True
return False
dis = random.randint(l, r)
if v[dis] == target:
return True
LeftPart = randomFind(v, 0, dis - 1, target)
RightPart = randomFind(v, dis + 1, r, target)
return LeftPart or RightPart不过话说回来，这种查找方式容易递归较深，性能也不高，仅仅当随机生成的下标对应的元素刚好等于目标值的时候可能稍微快点，所以说一切看命。