logo标签列表

在已排序的数组中寻找最佳插入位置的算法是O(log n)。

arraysalgorithmsortinglinked-list
12

我正在尝试制作一个算法，找到将目标插入已排序数组的最佳位置。

目标是返回项目在列表中存在的位置，否则返回它会进入的位置以保持列表排序。

所以说，假设我有一个列表：

   0   1   2   3   4    5    6
 ---------------------------------
 | 1 | 2 | 4 | 9 | 10 | 39 | 100 |
 ---------------------------------

我的目标项是14，它应该返回5的索引位置。

我目前拥有的伪代码:

array = generateSomeArrayOfOrderedNumbers()

number findBestIndex(target, start, end)
    mid = abs(end - start) / 2

    if (mid < 2) 
        // Not really sure what to put here
        return start + 1 // ??

    if (target < array[mid])
        // The target belongs on the left side of our list //
        return findBestIndex(target, start, mid - 1)
    else
        // The target belongs on the right side of our list //
        return findBestIndex(target, mid + 1, end)

我不太确定应该在这个时候放什么。我试图用二分搜索的方法来解决这个问题，但是经过五次重写后，这是我能想到的最好的解决方案。

9
二分查找是你需要的方法，只需使用一个简单的“while”循环即可，无需使用递归。 - Sergey Kalinichenko
@ldog：这实际上会使代码更加复杂（增加了一个if）。只需将基本情况设置为 start > end，并根据比较递归到 [start，mid] 或 [mid + 1，end]。请记住，我们不想找到 target，而是要找到 target 的后继者。 - Niklas B.
为什么这个问题被标记为“链表”？它的结构是数组还是链表？如果它是链表，那么二分查找就不起作用了，因为你需要随机访问才能从二分查找中受益，而链表没有这个功能。 - justhalf
@justhalf 嗯，从我的伪代码中你无法真正了解，但它的结构是链表。我自己特制的链表。嗯，更确切地说是一个链接集合。 - Brayden
正是因为我无法从你的伪代码中判断，所以才会问，哈哈。如果你的结构不支持随机访问（即访问需要O(n)时间），那么二分查找将比线性搜索慢O(n log n)。请确保在你的结构中访问任何元素都是O(1)。 - justhalf
显示剩余3条评论
7个回答
15

你的代码存在几个问题：

mid = abs(end - start) / 2

这不是在start和end之间的中间位置，而是它们之间距离的一半（向下取整为整数）。稍后使用它时就像它确实是一个有效的索引：

findBestIndex(target, start, mid - 1)

但这并不是正确的。你可能想使用mid = (start + end) // 2之类的内容。 同时，你会错过一些索引，因为跳过了中间值：


同时，你也会错过一些索引，因为你跳过了中间值：
return findBestIndex(target, start, mid - 1)
 ...
return findBestIndex(target, mid + 1, end)

你的基本情况现在必须表达得有些不同了。一个好的选择是条件

if start == end

因为现在你肯定知道你已经完成了搜索。请注意，您还应考虑数组中所有元素都小于target的情况，因此您需要将其插入到末尾。

我不常使用二分搜索，但如果用的话，就是这样

如果您以前没有使用过二分搜索，那么正确地实现它可能会出乎意料地困难。如果我进行二分搜索，我通常会使用以下模式：

lo, hi = 0, n // [lo, hi] is the search range, but hi will never be inspected.
while lo < hi:
    mid = (lo + hi) // 2
    if check(mid): hi = mid
    else:          lo = mid + 1

假设check是一个单调的二进制谓词（它总是在某个点之前为false，在那个点之后为true），在此循环之后，lo == hi 将是范围[0..n]中第一个满足check(lo) == true的数字。隐含地假设check(n)为真（这是该方法的一部分魔力）。

那么，什么是一个单调谓词，对于目标位置及其后面的所有索引都为true，而所有位置之前都为false呢？

如果我们考虑一下，我们想要找到数组中第一个大于目标值的数字，因此我们只需将其插入即可：

lo, hi = 0, n
while lo < hi:
    mid = (lo + hi) // 2
    if (a[mid] > target): hi = mid
    else:                 lo = mid + 1
return lo;
+1，有些人通常因为使用闭区间而感到困难，在大多数情况下，半开区间更容易使用，并且会产生更优雅的代码，就像在这种情况下一样。 - pasztorpisti
@Brayden：我对你的代码进行了一些分析，似乎有点出错。 - Niklas B.
@pasztorpisti：不，它适用于闭区间...循环不变式是第一个i使得check(i) == true在范围[lo..hi]内。 - Niklas B.
好的，试试这个：a=[0, 1, 2, 3] lo=0 hi=3 target=4 结果应该是4。 - pasztorpisti
让我们在聊天中继续这个讨论：http://chat.stackoverflow.com/rooms/48793/discussion-between-niklas-b-and-pasztorpisti - Niklas B.
显示剩余10条评论
3

这是我使用的代码：

int binarySearch( float arr[] , float x , int low , int high )
{
    int mid;
    while( low < high ) {
        mid = ( high + low ) / 2;
        if( arr[mid]== x ) {
            break;
        }
        else if( arr[mid] > x ) {
            high=mid-1;
        }
        else {
            low= mid+1;
        }
    }
    mid = ( high + low ) / 2;
    if (x<=arr[mid])
        return mid;
    else 
        return mid+1;
}

关键是即使低等于高，你也必须进行检查。

例如，请参考以下示例： 0.5->0.75 您要查找0.7或1的真实位置。

在两种情况下，当退出while循环时：low = high = 1，但其中一个应该放置在位置1，另一个应该放置在位置2。

1

我通过计算严格小于要插入的键的元素数量来解决了这个问题。检索到的计数是插入位置。以下是Java中可用的实现：

int binarySearchCount(int array[], int left, int right, int key) {
    if(left > right) {
        return -1; // or throw exception
    }
    int mid = -1;   //init with arbitrary value 

    while (left <= right) {
        // Middle element
        mid = (left + right) / 2;

        // If the search key on the left half
        if (key < array[mid]) {
            right = mid - 1;
        }
        // If the search key on the right half
        else if (key > array[mid]) {
            left = mid + 1;
        }
        // We found the key
        else {
            // handle duplicates
            while(mid > 0 && array[mid-1] == array[mid]) {
                --mid;
            }
            break;
        }
    }

    // return the number of elements that are strictly smaller (<) than the key
    return key <= array[mid] ? mid : mid + 1;
}
1
你走在正确的道路上。
首先，在 mid = abs(end + start) / 2 中，你不需要使用abs函数。
假设这里的abs表示绝对值，因为end应该始终不小于start，除非你的代码有误。所以这里的abs没有帮助，但可能会潜在地隐藏你的问题，使得调试变得困难。
你也不需要 if (mid < 2) 这一部分，mid小于两个数值并没有什么特别之处。
array = generateSomeArrayOfOrderedNumbers()

int start = 0;
int end = array.size(); 

int findBestIndex(target, start, end){

if (start == end){   //you already searched entire array, return the position to insert
  if (stat == 0) return 0; // if it's  the beginning of the array just return 0.
  if(array[start] > target) return start -1; //if last searched index is bigger than target return the position before it.
else return start;
}
mid = (end - start) / 2

// find correct position 
if(target == array[mid]) return mid;

if (target < array[mid])
{
 // The target belongs on the left side of our list //
return findBestIndex(target, start, mid - 1)
}
else
{
 // The target belongs on the right side of our list //
 return findBestIndex(target, mid + 1, end)
}
}
1
以下是用于从有序数组中搜索目标值（它包含重复值）的代码。它返回可以插入目标值的位置数组。希望这段代码能在任何方面对您有所帮助。欢迎提出任何建议。
static int[] climbingLeaderboard(int[] scores, int[] alice) {
    int[] noDuplicateScores = IntStream.of(scores).distinct().toArray();
    int[] rank = new int[alice.length];

    for (int k = 0; k < alice.length; k++) {
        int i=0;
        int j = noDuplicateScores.length-1;
        int pos=0;
        int target = alice[k];
        while(i<=j) {
            int mid = (j+i)/2;
            if(target < noDuplicateScores[mid]) {
                i = mid +1;
                pos = i;
            }else if(target > noDuplicateScores[mid]) {
                j = mid-1;
                pos = j+1;
            }else {
                pos = mid;
                break;
            }
        }
        
        rank[k] = pos+1;
    }

    return rank;
 }
0

这里有一个使用Python调整二分查找的解决方案。

def func(x, y):
    start = 0
    end = len(x)
    while start <= end:
        mid = (start + end)//2
        print(start, end, mid)
        if mid + 1 >= len(x):
            return mid + 1
        if x[mid] < y and x[mid + 1] > y:
            return mid + 1
        elif x[mid] > y:
            end = mid - 1
        else:
            start = mid + 1
    return 0

func([1,2,4,5], 3)
0

使用稍作修改的二分查找算法的Java解决方案

int findInsertionIndex(int[] arr, int t) {
    int s = 0, e = arr.length - 1;
  
    if(t < arr[s])return s;
    if(t > arr[e])return e;

      while (s < e){

        int mid = (s + e)/2;

        if(arr[mid] >= t){
            e = mid - 1;
        }

        if(arr[mid] < t){
            s = mid + 1;
        }
      }

    return arr[s] < t? s + 1 : s;
 }

上述代码适用于以下可能的情况：

  • 如果 arr[mid] > target -> 目标索引位于左半部分，找到目标的第一个最大值的索引并返回它。
  • 如果 arr[mid] < target -> 目标索引位于右半部分，找到目标的第一个最小值的索引并返回索引+1以指向目标/插入索引。
  • 如果 arr[mid] == target -> 找到目标值的第一次出现的索引并返回它。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接