Can a randomized binary search have an O(1) complexity at least in practice?
作者：
Highlights：
•
摘要
The note suggests the possibility for a randomized binary search to have an O(1) complexity at least in practice provided only that the element being searched for is a random integer less than or equal to the array size and hence or otherwise when the probability of its presence in the array is a near unity.
论文关键词：Randomized binary search,Empirical O(1) complexity
论文评审过程：Available online 12 January 2007.
论文官网地址：https://doi.org/10.1016/j.amc.2006.12.079
