使用二进制搜索与重复的排序数组 [英] Using Binary Search with sorted Array with duplicates

问题描述

我的任务是创建一个方法来打印所有的索引，其中的值x在排序的数组中被找到。

我明白，如果我们刚刚扫描从0到N（数组长度）的数组，它的运行时间将为O（n）最差。由于将传入方法的数组将被排序，我假设我可以利用二进制搜索，因为这将是O（log n）。但是，仅当数组具有唯一值时才有效。由于二进制搜索将在首次查找特定值之后完成。我正在考虑在排序数组中进行二进制搜索以查找x，然后检查该索引之前和之后的所有值，但是如果数组包含所有x值，那么似乎不会那么好。

我想我在问的是，有没有更好的方法来找到一个比O（n）更好的排序数组中的特定值的所有索引？

  public void PrintIndicesForValue42（int [] sortedArrayOfInts）
 {
 //通过sortedArrayOfInts 
 
 //打印所有索引，我们找到数字42. 
} 
  

Ex：sortedArray = {1，13，42，42，42，77，78}将打印：在索引中找到42：2,3,4

解决方案

嗯，如果你真的有一个排序的数组，你可以进行一个二进制搜索，直到找到你要查找的索引之一，其余的应该很容易找到，因为它们都在旁边另一个。

一旦找到你的第一个，你比之前找到所有的实例，然后是所有的实例。

使用该方法您应该得到大致 O（lg（n）+ k）其中 k 是数字您要搜索的值的出现次数。

编辑：

而不，您将永远无法访问所有 k 值小于 O（k）时间。

第二次编辑，以便我能感觉到实际上我提供了一些有用的东西：

而不是搜索X的第一个和最后一个出现，而不是你可以进行二次搜索第一次发生和一个二进制搜索最后一次发生。这将导致 O（lg（n））总数。一旦你这样做，你会知道所有的索引之间也包含X（假设它被排序）

你可以通过搜索检查是否值等于 x ， AND 检查左侧的值（或右侧，取决于您是要查找第一次出现还是最后一次）等于 x 。

I've been tasked with creating a method that will print all the indices where value x is found in a sorted array.

I understand that if we just scanned through the array from 0 to N (length of array) it would have a running time of O(n) worst case. Since the array that will be passed into the method will be sorted, I'm assuming that I can take advantage of using a Binary Search since this will be O(log n). However, this only works if the array has unique values. Since the Binary Search will finish after the first "find" of a particular value. I was thinking of doing a Binary Search for finding x in the sorted array, and then checking all values before and after this index, but then if the array contained all x values, it doesn't seem like it would be that much better.

I guess what I'm asking is, is there a better way to find all the indices for a particular value in a sorted array that is better than O(n)?

public void PrintIndicesForValue42(int[] sortedArrayOfInts)
{
    // search through the sortedArrayOfInts

    // print all indices where we find the number 42. 
}

Ex: sortedArray = { 1, 13, 42, 42, 42, 77, 78 } would print: "42 was found at Indices: 2, 3, 4"

解决方案

Well, if you actually do have a sorted array, you can do a binary search until you find one of the indexes you're looking for, and from there, the rest should be easy to find since they're all next to each-other.

once you've found your first one, than you go find all the instances before it, and then all the instances after it.

Using that method you should get roughly O(lg(n)+k) where k is the number of occurrences of the value that you're searching for.

EDIT:

And, No, you will never be able to access all k values in anything less than O(k) time.

Second edit: so that I can feel as though I'm actually contributing something useful:

Instead of just searching for the first and last occurrences of X than you can do a binary search for the first occurence and a binary search for the last occurrence. which will result in O(lg(n)) total. once you've done that, you'll know that all the between indexes also contain X(assuming that it's sorted)

You can do this by searching checking if the value is equal to x , AND checking if the value to the left(or right depending on whether you're looking for the first occurrence or the last occurrence) is equal to x.

这篇关于使用二进制搜索与重复的排序数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！