扩展二进制搜索算法以查找要在数组中搜索的键值的第一个和最后一个索引-Java 学习之路

问题是扩展二进制搜索算法以最有效的方式查找排序数组中所有出现的目标值 . 具体地说，算法的输入是（1）整数的排序数组，其中一些数字可能出现不止一次，以及（2）要搜索的目标整数 . 算法的输出应该是一对索引值，指示数组中第一次和最后一次出现的整数（如果确实发生的话） . 源代码可以在c＃，c，c中 .

此外，我们可能需要查找索引的最大和最小比较数是多少？

7 回答

6
如果你有点聪明，你可以定义两个不同的二进制搜索功能 . 一个将返回搜索值的第一个外观的索引，另一个将返回搜索值的最后一个外观 . 根据您对二进制搜索的了解，您应该能够确定最大和最小比较次数 .

在我看来，使用两个二进制搜索应该是平均最快的方法 . 例如，如果您只使用一个二进制搜索来查找第一个项目并在之后线性搜索，则最坏的情况是整个函数是相同的值 . 对于长度为10000的数组，这将在最坏的情况下进行10013次比较，而使用两次二进制搜索将在最坏的情况下为同一阵列进行28次比较 . 当然，使用相同大小的数组，二进制/线性搜索方法的最佳情况是14次比较，而两种二进制搜索方法的最佳情况是26次比较 .

**更新

好的，这是一个二进制搜索，用于查找数组中元素的第一个外观 . 我会给你一个递归函数（你当然可以迭代并以其他方式优化它） . 这将在int的数组a中搜索int val . 另外，我没有注意找到中点（如果阵列非常大，可能会出现问题） .
```
int bs1(int a[], int val, int left, int right)
{
    if(right == left) return left;
    int mid = (right+left)/2;

    if(val > a[mid]) return bs1(a, val, mid+1, right);
    else return bs1(a, val, left, mid);
}
```
但是，您应该在返回一个它实际引用正确值的索引后进行检查，因为如果val不在数组中，则返回的索引将对应于大于val的下一个元素 .

对此进行一些细微的更改将使函数找到最后一个元素 . 这样做的关键是正确使用比较器并记住整数除法总是截断 .
回复于 2024-04-25T07:29:38+08:00
2

对于C，您可以查找 std::equal_range() 及其复杂性要求 . 只要您对基本算法感兴趣，无论实现的语言使用是什么，都应该应用相同的一般规则 .

回复于 2024-04-25T07:29:38+08:00

如果不编写自己的二进制搜索算法，通过重复调用标准算法，这很容易做到 .

// some curly-bracket language:

// int BinarySearch(sortedList, searchIndex, searchLength, valueToFind)
// returns the zero-based index of the item in the list, or a negative value
// if the item is not found

int inner = BinarySearch(list, 0, listSize, value);
if(inner < 0){
    // handle case where value is not found in list
}

int bottom = inner, top = inner;
while(true){
    int i = BinarySearch(list, 0, bottom, value);
    if(i < 0)
        break;
    bottom = i;
}
while(true){
    int i = BinarySearch(list, top + 1, listSize - top - 1, value);
    if(i < 0)
        break;
    top = i;
}

// bottom and top now hold the bounds of all instances of value in list

这与您使用自定义算法获得的效率非常接近，除了您有更多的函数调用开销 .

至于比较次数，我只需要2 * log2N，其中N是列表中的项目数 .

Edit

呸!它不是2 * log2N，因为与自定义算法不同，它不会逐步排除列表的某些部分 . 似乎1最大比较计数是（log2N-0.5）* log2N . 对于包含230个元素的列表（对于220 N的390个比较和对于210 N的95个），这仍然只有885个比较，但我们可以做得更好 .

// int Compare(a, b)
// returns 0 if a and b are equal,
//         a negative value if a < b, or
//         a positive value if a > b

int start = 0, end = listSize, inner;

while(true){
    if(end == start){
        // handle case where value is not found in list
    }
    inner = (start + end) / 2;
    int cmp = Compare(list[inner], value);
    if(cmp == 0)
        break;
    if(cmp < 0)
        start = inner + 1;
    else end = inner;
}

int top = inner, bottom = inner;

while(true){
    if(start >= bottom)
        break;
    inner = (start + bottom) / 2;
    int cmp = Compare(list[inner], value);
    if(cmp == 0)
        bottom = inner;
    else start = inner + 1;
}

while(true){
    if(end - 1 <= top)
        break;
    inner = (top + 1 + end) / 2;
    int cmp = Compare(list[inner], value);
    if(cmp == 0)
        top = inner;
    else end = inner;
}

这将最多进行2 * log2N比较 . 230个项目最多需要60个比较，220个项目最多需要40个比较等 .

1我通过实验确定了这一点 . 我不够聪明，无法用数学方法解决这个问题 .

回复于 2024-04-25T07:29:38+08:00

1

您可以在Bentley Programming Pearls和Knuth的Vol.3：排序和搜索中找到关于此的讨论 .

这是C中的一个实现：http://the-algo-blog.blogspot.com/2011/06/binary-search-to-find-last-and-first.html

回复于 2024-04-25T07:29:38+08:00
0
对于问题中最有效的部分，没有干净的答案 . 这将取决于预期有多少具有相同值的条目 . 如果只是在找到一个元素之后在数组的两个直接中进行线性搜索将是你最快的选择，但如果你期望很多具有相同值的条目你可以做一些二进制搜索来找到开始结束指数 .

免责声明：未经测试;它旨在表明这个想法，而不是直接用作生产环境代码
```
int org = binarySearch(array,value) //do the binary search and find on element
int min = org-delta; //delta is some constant based on how many elemts are to be expected
int max = org;
min = min < 0 ? 0 : min;
int search= min;
bool latestWasHit = false;
while(search > 0)
{
  if(search+1 == max)
     return max;
  if(array[search] != value)
  {
     min = search;
     search = search + (max-search)/2
  }
  else
  {
     max = search;
     search = (search-min)/2;
  } 
}
```
然后反过来上限 . 但是它需要相当多的元素在此之前比简单的线性搜索更快 .
回复于 2024-04-25T07:29:38+08:00
0
我想普通算法会有这样的东西：
```
if(value == test) return;
if(value < test) min = i;
if(value > test) max = i;
```
一旦您使用它来查找其中一个值，使用您当前必须的最小值和最大值来执行两个稍微模式的二进制搜索，以查找提示 .

要找到最顶层的替换上面的：
```
if(value <= test) min = i;
if(value > test) max = i;
```
最底层替换为：
```
if(value >= test) max = i;
if(value < test) min = i;
```
请注意，使用此方法没有提前返回，您只需继续操作，直到最小值和最大值分别为一个或多个，我想您可以添加另一个检查
```
if(value == test and arr[i-1] != test) return;
```
等等
回复于 2024-04-25T07:29:38+08:00

我创建了两个二进制搜索方法，分别返回第一次和最后一次出现 .

public static void main(String[] args) {
    int a[] ={1,2,2,2,2,2,5,5,6,8,9,10};

    System.out.println(5+" first = "+first(a, 5, 0, a.length-1));
    System.out.println(5+" last = "+right(a, 5, 0, a.length-1));

    System.out.println(1+" first = "+first(a, 1, 0, a.length-1));
    System.out.println(1+" last = "+right(a, 1, 0, a.length-1));

    System.out.println(2+" first = "+first(a, 2, 0, a.length-1));
    System.out.println(2+" last = "+right(a, 2, 0, a.length-1));

    System.out.println(10+" first = "+first(a, 10, 0, a.length-1));
    System.out.println(10+" last = "+right(a, 10, 0, a.length-1));

    System.out.println(8+" first = "+first(a, 8, 0, a.length-1));
    System.out.println(8+" last = "+right(a, 8, 0, a.length-1));

    System.out.println(11+" first = "+first(a, 11, 0, a.length-1));
    System.out.println(11+" last = "+right(a, 11, 0, a.length-1));


}

private static int first(int [] a, int x, int l, int h){
    if(l>h){
        return -1;
    }
    int mid = (h-l)/2+l;
    if(a[mid] == x && (mid==0 || a[mid-1] != x) ){
        return mid;
    }else if(a[mid] == x){
        return first(a, x, l, mid-1);
    }else if(a[mid]>x){
        return first(a, x, l, mid-1);
    }else{
        return first(a, x, mid+1, h);
    }
}


private static int right(int [] a, int x, int l, int h){
    if(l>h){
        return -1;
    }
    int mid = (h-l)/2+l;
    if(a[mid] == x && (mid==a.length-1 || a[mid+1] != x) ){
        return mid;
    }else if(a[mid] == x){
        return right(a, x, mid+1, h);
    }else if(a[mid]>x){
        return right(a, x, l, mid-1);
    }else{
        return right(a, x, mid+1, h);
    }
}

Output:
    1 first = 0
    1 last = 0
    2 first = 1
    2 last = 5
    10 first = 11
    10 last = 11
    8 first = 9
    8 last = 9
    11 first = -1
    11 last = -1

回复于 2024-04-25T07:29:38+08:00

扩展二进制搜索算法以查找要在数组中搜索的键值的第一个和最后一个索引

7 回答

相关问题