在没有重复的顺序数据中进行二分查找
Binary search in sequential data without repetitions
我正在考虑以下问题，
给定一个大小为 n 的排序数组，其中包含没有重复的整数，我们是否可以使用 属性 即
- a) 没有重复项
- b) 两个相邻整数之间没有整数（即在 50 之后要么有 51，要么 51 不在数组中）
思路是当你遇到一个值时，你添加一个测试，看你寻找的值是否与当前值相邻（+或-1），如果是，则减少搜索间隔而不是减半到一个点，当前中点旁边的索引。
例如，假设你有一个数组 tab[i]=i 用于所有索引并且所有值从 0 到 99。我们寻找 51，第一个 mid 是 50，所以正常的二进制搜索是7 次命中中的最坏情况 (log2 (100))。通过附加测试，我们测试 50，并将搜索间隔减少到 50 的邻居，因此分两步完成（但有附加测试）。
这是一个例子，但不代表我的数据集，另一个例子可能是 {0,13223,13225,42341,42342} 或任何一组没有重复排序的值。只是为了提供一些上下文，我正在操作的这些数组是稀疏数组实现中的键（非空索引）。
在最坏的情况下，似乎我们在间隔大小为 3 而不是 2 时得出结论，因此 log2(n)-1 测试。
在代码中，这会给出类似（Java 此处使用）以 0 作为 lo 和 array-1 的长度作为 hi 调用来搜索整个数组：
// This is Arrays.binarySearch(), but doesn't do any argument validation.
static int binarySearchGT(int[] array, int value, int lo, int hi) {
while (lo <= hi) {
final int mid = (lo + hi) >>> 1;
final int midVal = array[mid];
if (midVal < value) {
lo = mid + 1;
} else if (midVal > value) {
hi = mid - 1;
} else {
return mid; // value found
}
}
return ~lo; // value not present
}
变成
static int binarySearch(int[] array, int value, int lo, int hi) {
while (lo <= hi) {
final int mid = (lo + hi) >>> 1;
final int midVal = array[mid];
if (midVal < value) {
if (hi != mid && midVal == value -1) {
hi = mid + 1;
}
lo = mid + 1;
} else if (midVal > value) {
if (lo != mid && midVal == value + 1) {
lo = mid - 1;
}
hi = mid - 1;
} else {
return mid; // value found
}
}
return ~lo; // value not present
}
在这个特定的 discrete/non 重复输入案例中，我认为这应该（总是）比正常的二进制搜索更好的推理是否正确？我确实看到我有一个额外的分支和两个布尔测试，包括一个加法，但仍然有大量输入，你能展示这个策略显然最糟糕的情况吗？
有人知道文献中提到过某种类似的想法吗？
[编辑以更好地解释并非所有元素都存在]
因为你不能保证数组中会有一个与搜索内容相邻的值，在最坏的情况下没有，这意味着成本是相同的作为二进制搜索。更糟糕的是，实际上，因为您为检查的每个元素都添加了额外的测试。
所以，二进制搜索：我们得到 ~log2(n) 搜索给定序列的原因是因为我们在每次递归时将序列分成 2 组，所以我们在树深度 log2(n ).比如说，我们有有序的数字序列 [0,63] 作为一个集合，然后我们拆分以找到 39 如下所示：
普通二分查找
value = 39
Step 1: [0,63], split at 32
Step 2: [32-63], split at 48
Step 3: [32-47], split at 40
Step 4: [32-39], split at 36
Step 5: [36-39], split at 38
Step 6: [38-39], split at 39
Step 7: Found 39
你的算法
value = 39
Step 1: [0,63], split at 32
Step 2: [32-63], split at 48
Step 3: [32-47], split at 40
Step 4: [32-39], split at 36
Step 5: [36-39], split at 38
Step 6: Found 39
如您所见，在最坏的情况下，我们所做的只是将树的最大深度降低 1，但我们将每个深度的测试数量增加了 2 倍。你的算法需要12次测试才能找到值，而传统的二分查找只需要7次。最终，时间复杂度仍然是O(log(n))，但系数更差。在每种情况下，最坏情况下的性能都比传统的二分查找差。
这里的问题是您假设 二元搜索 的最坏情况 仍然是最坏情况-case 算法的场景，实际上它是算法的 best-case 场景。
我正在考虑以下问题，
给定一个大小为 n 的排序数组，其中包含没有重复的整数，我们是否可以使用 属性 即
- a) 没有重复项
- b) 两个相邻整数之间没有整数（即在 50 之后要么有 51，要么 51 不在数组中）
思路是当你遇到一个值时，你添加一个测试，看你寻找的值是否与当前值相邻（+或-1），如果是，则减少搜索间隔而不是减半到一个点，当前中点旁边的索引。
例如，假设你有一个数组 tab[i]=i 用于所有索引并且所有值从 0 到 99。我们寻找 51，第一个 mid 是 50，所以正常的二进制搜索是7 次命中中的最坏情况 (log2 (100))。通过附加测试，我们测试 50，并将搜索间隔减少到 50 的邻居，因此分两步完成（但有附加测试）。
这是一个例子，但不代表我的数据集，另一个例子可能是 {0,13223,13225,42341,42342} 或任何一组没有重复排序的值。只是为了提供一些上下文，我正在操作的这些数组是稀疏数组实现中的键（非空索引）。
在最坏的情况下，似乎我们在间隔大小为 3 而不是 2 时得出结论，因此 log2(n)-1 测试。
在代码中，这会给出类似（Java 此处使用）以 0 作为 lo 和 array-1 的长度作为 hi 调用来搜索整个数组：
// This is Arrays.binarySearch(), but doesn't do any argument validation.
static int binarySearchGT(int[] array, int value, int lo, int hi) {
while (lo <= hi) {
final int mid = (lo + hi) >>> 1;
final int midVal = array[mid];
if (midVal < value) {
lo = mid + 1;
} else if (midVal > value) {
hi = mid - 1;
} else {
return mid; // value found
}
}
return ~lo; // value not present
}
变成
static int binarySearch(int[] array, int value, int lo, int hi) {
while (lo <= hi) {
final int mid = (lo + hi) >>> 1;
final int midVal = array[mid];
if (midVal < value) {
if (hi != mid && midVal == value -1) {
hi = mid + 1;
}
lo = mid + 1;
} else if (midVal > value) {
if (lo != mid && midVal == value + 1) {
lo = mid - 1;
}
hi = mid - 1;
} else {
return mid; // value found
}
}
return ~lo; // value not present
}
在这个特定的 discrete/non 重复输入案例中，我认为这应该（总是）比正常的二进制搜索更好的推理是否正确？我确实看到我有一个额外的分支和两个布尔测试，包括一个加法，但仍然有大量输入，你能展示这个策略显然最糟糕的情况吗？
有人知道文献中提到过某种类似的想法吗？
[编辑以更好地解释并非所有元素都存在]
因为你不能保证数组中会有一个与搜索内容相邻的值，在最坏的情况下没有，这意味着成本是相同的作为二进制搜索。更糟糕的是，实际上，因为您为检查的每个元素都添加了额外的测试。
所以，二进制搜索：我们得到 ~log2(n) 搜索给定序列的原因是因为我们在每次递归时将序列分成 2 组，所以我们在树深度 log2(n ).比如说，我们有有序的数字序列 [0,63] 作为一个集合，然后我们拆分以找到 39 如下所示：
普通二分查找
value = 39
Step 1: [0,63], split at 32
Step 2: [32-63], split at 48
Step 3: [32-47], split at 40
Step 4: [32-39], split at 36
Step 5: [36-39], split at 38
Step 6: [38-39], split at 39
Step 7: Found 39
你的算法
value = 39
Step 1: [0,63], split at 32
Step 2: [32-63], split at 48
Step 3: [32-47], split at 40
Step 4: [32-39], split at 36
Step 5: [36-39], split at 38
Step 6: Found 39
如您所见，在最坏的情况下，我们所做的只是将树的最大深度降低 1，但我们将每个深度的测试数量增加了 2 倍。你的算法需要12次测试才能找到值，而传统的二分查找只需要7次。最终，时间复杂度仍然是O(log(n))，但系数更差。在每种情况下，最坏情况下的性能都比传统的二分查找差。
这里的问题是您假设 二元搜索 的最坏情况 仍然是最坏情况-case 算法的场景，实际上它是算法的 best-case 场景。