已排序数组中具有重复项的数字的下限

Question

好的，所以数组中数字的下限被定义为数组中小于所提供数字的最大数字。如果我们在数组中找到它，我们返回它的索引，否则 -1。

例如，arr = {1, 2, 4, 4, 4, 6, 8, 10, 12}。 情况 1，target = 4。输出为 1（因为 arr[1] 是小于 target 的最大数字）。 情况 2，target = 13。输出为 8（因为 arr[8] 是小于 target 的最大数字）。 情况 3，目标 = 0。输出为 -1（因为没有大于 0 的元素）。

对于没有任何重复项的数组，它只是一个二分查找并返回高1，我们得到的时间复杂度为O(n)。

但是对于有重复的数组，进行二分查找后，时间复杂度趋于O(n)，因为我必须线性回溯才能得到不等于目标本身的最小元素。

例如，arr = {1, 2, 4, 4, 4, 6, 8, 10, 12}。 情况 1，目标 = 4。 二分查找给我索引 4，因为 arr[4] = 4。但是我必须遍历回来才能得到小于目标的最大数字。

有什么东西可以帮助我消除线性搜索而只具有 log2(n) 时间复杂度吗？

Answer 1

最后我还附上了视频

算法：

• 通过名称 lower_bound 声明一个变量。该变量表示 arr[i] >= target 的最小索引，并将在函数执行后返回。

• 将 lower_bound 设置为 arr.size。这是因为，如果我们的目标大于 arr 中的最大元素，则 lower_bound 将比最大索引大 1，因为我们希望 arr[lower_bound] >= target。例如，如果 target = 13，并且 arr[arr.size - 1] = 12。因此将返回 arr.size。

• 现在我们执行二分查找。如果 arr[mid] >= target，我们需要缩短搜索空间，因为我们的索引较小。

• 如果到达[中]< target, we set low = mid + 1.

示例：

如果仅拿上面的例子，arr = {1, 2, 4, 4, 4, 6, 8, 10, 12} 且 target = 4, 那么下界将是索引 2，因为 2 是 arr[i] >= target 的最小索引。

• 最初，lower_bound = arr.size = 9。
• 我们执行二分查找，low = 0，high = arr.size - 1。
• mid = 4，现在 arr[mid] 也等于 4，因此 arr[mid] >= target，我们设置 high = mid - 1 和 lower_bound = 4。
• mid = 2，再次 arr[mid] = 4，因此，high = mid - 1 且 lower_bound = 2。
• mid = 1，现在 arr[mid] < target, therefore low = mid + 1.
• 现在最低价和最高价位于相同的索引 2。我们返回也等于 2 的 lower_bound。

同样的方法也可以求出上界。在上限的情况下，它应该是 arr[i] > target，而不是 arr[i] >= target。

我在youtube上找到的视频解释