O(log n) 算法在排序数组中找到最佳插入位置

问题描述 投票：0回答：8

我正在尝试制定一种算法，找到将 target 插入已排序数组的最佳位置。

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

所以说我有一个清单：

   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)

我现在不太确定该放什么。我尝试采用二分搜索方法来解决此问题，但这是我在重写 5 次左右后能想到的最好方法。

arrays algorithm sorting linked-list
8个回答
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;
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
投票

您走在正确的道路上。

首先，你不需要腹肌

mid = abs(end + start) / 2

假设这里的abs表示绝对值，因为end应该总是不小于start，除非你的代码中有一些错误。所以这里的abs毫无帮助，但可能会隐藏你的问题，使调试变得困难。

您也不需要

if (mid <  2)
部分，中型小于两个没有什么特别的。 

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
投票

我通过计算严格较小的元素数量解决了这个问题（<) than the key to insert. The retrieved count is the insert position. Here is a ready to use implementation in 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
投票

下面是用于从排序数组（包含重复值）中搜索目标值（数组列表）的代码。

它返回我们可以插入目标值的位置数组。

希望这段代码对您有任何帮助。

欢迎任何建议。

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 -> target索引位于左半部分，则找到target的第一个最大值的索引并返回。
  • 如果arr[mid]< target ->目标索引位于右半部分，则找到目标的第一个最小值的索引，并返回索引+1以指向目标/插入索引。
  • if arr[mid] == target -> 找到目标值第一个出现的索引并返回它。
0
投票

对于那些寻找相同内容但使用字符串获取索引以将字符串插入到排序列表中的人，这里是我正在使用的 C#，它基于 Niklas B 当前接受的答案中提供的算法。

/// <summary>
/// Gets the index in the sorted data to use when inserting the given string.
/// If the result is > the number of items in the data, the string should
/// be appended to the list.
/// </summary>
/// <param name="insert">The string to insert</param>
static int GetSortedIndex(string[] data, string insert)
{
    int low = 0;
    int high = data.Length;

    while (low < high)
    {
        int mid = (low + high) / 2;

        if (string.Compare(data[mid], insert, StringComparison.OrdinalIgnoreCase) > 0)
            // The item at index "mid" is alphabetically > than the string to insert
            high = mid;
        else
            low = mid + 1;
    }

    return low;
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.