未知班次的二进制搜索修改-Java 学习之路

假设我有一个排序数组[1,2,3,4,5,6] . 我可以应用二进制搜索来查找任何数字，但我的二进制搜索逻辑中的修改我必须做什么如果我的排序数组向左移动了一些未知数字 . 像[4,5,6,1,2,3] .

5 回答

6
- 我们可以使用二分搜索找到班次 . 我们需要找到第一个小于给定数组的第一个元素的数字 . 像这样的东西：
```
def getShift():
    if a[n - 1] > a[0]:
         return 0 // there is no shift
    low = 0 // definitely not less than a[0]
    high = n - 1 // definitely less than a[0]
    while high - low > 1:
        mid = (low + high) / 2
        if a[mid] < a[0]:
            high = mid
        else
            low = mid
    return high
```
- 现在知道班次，所以我们可以在两个时间间隔内运行标准二进制搜索： [0, shift) 和 [shift, n - 1] .
时间复杂度是 O(log n) （因为我们运行3次二进制搜索） .
回复于 2024-04-28T08:27:38+08:00
0

只需在未知班次后重新排序数组 . 它的计算成本很高，但它是正确的 .

此外，您还可以在此处进行线性排序，因为排序和搜索将采用O（n * log（n）） . 通过强力进行线性搜索只会是O（n） .

回复于 2024-04-28T08:27:38+08:00

您只需要运行常规二进制搜索算法一次，并在逻辑上修改何时选择上部或下部搜索窗口 . 修改基于与移位数组中第一个元素的额外比较，以便您知道所在阵列的哪个部分 . 您可以执行此操作而无需实际找到拆分的精确位置 .

在红宝石中：

LIST = [6,7,8,9,10,1,2,3,4,5]

def binary_search(x)
  first = LIST[0]
  low = 0
  high = LIST.size-1
  while low <= high
    mid = low + (high-low)/2 # avoid overflow
    return mid if x == LIST[mid]
    if (LIST[mid] < first) != (x < first) || LIST[mid] < x
      low = mid + 1
    else
      high = mid - 1
    end
  end
  return -1 # not found
end

1.upto(10) do |x|
  puts "#{x} found at index #{binary_search(x)}"
end

输出：

1 found at index 5
2 found at index 6
3 found at index 7
4 found at index 8
5 found at index 9
6 found at index 0
7 found at index 1
8 found at index 2
9 found at index 3
10 found at index 4

回复于 2024-04-28T08:27:38+08:00

0
方法1

实际上有一个未知的转变，你仍然可以做二进制，但它有点不稳定 .

一种方法是将列表的大小加倍，即：
```
[4,5,6,   1,2,3, 4,5,6,   1,2,3]
# basically  mylist.extend(mylist)
```
正如你所看到的，我只是将尺寸加倍，但中间部分仍然是有序的 .

现在你可以查看列表直到
```
list[i-1] > list[i]
```
这将是您开始二进制搜索，最后相同的数量将是二进制列表的结尾 .
```
start = i
end = len(list) -1
```
现在你可以进行二进制搜索了

根据数据平均值可能会低于 O(n)

方法2

您可以使用列表并执行二进制搜索：

O(nlog(n)) + log(n)

方法3

线性搜索所有元素

O(n)
回复于 2024-04-28T08:27:38+08:00
1
只需简单的二进制搜索，无需加倍或排序或任何其他数组预处理

让我们开始吧
```
l = 0; 
r = n-1;
```
和
```
m = (l + r)/2
```
如果我们要搜索的 Value 比：

1）if（l和m之间没有跳转）
```
array[l] < v < array[m] or
```
（如果在l和m之间有跳跃）
```
v < array[m] < array[l] or  
array[m] < array[l] < v
```
比v在l和r之间，我们可以使r = m

2）如果v等于array [l] array [r]或array [m]，我们就找到了它

3）在所有其他情况下，v介于m和r之间，我们可以使l = m

4）重复新的l和r
回复于 2024-04-28T08:27:38+08:00

未知班次的二进制搜索修改

5 回答

方法1

方法2

方法3

相关问题