1. 首页
  2. 问答
  3. C中的二进制搜索无法正常工作

C中的二进制搜索无法正常工作

2013-02-19 50 views
1 
int recurbinarysearch(int * oringalary, int low, int high, int target) { 

    if (low > high) { 
     return -1; 
    } else { 
     int mid = (low + high)/2; 
     if (target == * (oringalary + mid)) return mid; 
     if (target > * (oringalary + mid)) return recurbinarysearch(oringalary, mid + 1, high, target); 
     if (target < * (oringalary + mid)) return recurbinarysearch(oringalary, low, mid - 1, target); 
    } 
}

有没有人在我的递归二分搜索算法中看到错误？偶尔它会返回一个不正确的索引（通常它是关闭的），但是偶尔会停下来。但通常情况下，这是正确的。我没有看到这个问题，希望能得到帮助。C中的二进制搜索无法正常工作

来源

2013-02-19 SystemFun

+0

您确定该数组已排序？ – nhahtdh 2013-02-19 04:17:42

+0

Yup几乎100％的数组被打印出来，它似乎被正确排序。 – SystemFun 2013-02-19 04:19:08

+0

是否有可能是由于分割（低+高）/ 2导致的某种累积舍入误差？ – 2013-02-19 04:22:36

回答

1

编辑这是接受的，所以我想我应该真的尝试把它变成一个正确的答案。

我原先假定（见“注意”以下），问题是使用半开放边界。它实际上（正确）使用包括范围。在最初的通话中，low=0和high=n-1。

使用包含边界通常被认为是一件坏事 - 请参阅Dijkstra的经典（PDF）。在C族语言中，半开放边界是一个常见的约定，甚至优于而不是for (i = 0; i <= n-1; i++)。但是，考虑到使用包容性边界，问题中的代码似乎是正确的。

正如WhozCraig在评论中发现的那样，调用代码并不尊重该惯例，并且传递了错误的界限 - 包括搜索范围内的超出界限的垃圾项。由于该额外项目是垃圾，所以范围内的项目被排序的假设也可能失效。大多数搜索不会找到该垃圾项目（因为您不太可能搜索它拥有的任何垃圾值），但会导致搜索错误。

注意这可能不是一个答案，但它是一个评论太长。

您的界限是否包容，独占或半开？

我打算假设半开放 - 包括low，排除在high。如果是这样，这条线看起来错了...

if (target < * (oringalary + mid)) 
    return recurbinarysearch(oringalary, low, mid - 1, target);

原因是你已经在mid检查项目，但你使用mid - 1作为新独家上限。这意味着mid - 1中尚未检查的项目已被意外排除在搜索之外。该行应该是...

if (target < * (oringalary + mid)) 
    return recurbinarysearch(oringalary, low, mid, target);

这使得该项目在mid - 1搜索范围。由于上限是独占的，因此mid的项目将不会再次搜索。

弄乱二进制搜索的界限是一个常见问题，它会导致比它看起来应该更多的错误。

然而，这本身并不说明你的症状 - 它应该无法找到项目 有时（大概50％左右的搜索） 了很多，但它不应该报告为成功搜索到错误的位置。

在二进制搜索中出现错误边界的常见症状是无限循环（由于未从边界中排除同一项目而被重复检查）或搜索无法找到存在的项目（因为项目已从搜索中排除范围没有被检查）。

说实话，我看不出你的症状如何发生。函数退出的每种可能方式都应该给出正确的成功结果，否则将导致失败结果。我能想到的唯一可能的例外是该代码之外 - 误解结果，例如，未能检查-1的结果。

顺便说一句 - 这是我代表妓女我的问题和回答关于one-comparison-per-iteration binary search的绝佳机会。

编辑我想我发现了另一个问题与界限 - 仍然假设半开，这条线是错误的...

if (low > high) {

，应该是...

if (low >= high) {

原因是，对于半开放边界，如果边界相等，则两者之间没有项目需要检查 - 即使低边界项目无效，因为高限等于它并且是独占的。这允许您仍然测试

来源

2013-02-19 05:01:46 Steve314

+0

+1当我第一次看到问题时，我实际上认为这些索引看起来不完整。我习惯于这样做一个单一指针和上限，即'bs（ar，len）'计算mid，然后在发现时返回true，或返回'bs（ar，mid）'或'bs（ar + mid，len-mid）'，但这更多的是确定存在而不是获取实际的*值*。感谢您接受这一点。 – WhozCraig 2013-02-19 05:09:25

+0

我认为在这个特定的实现中边界是包容的。在这种情况下，如果最初进入包容性边界*，它们将正确工作。正如OP所言，他错误地通过了半开放的界限。 – nneonneo 2013-02-19 05:42:16

1

有关二分查找的详细讨论，请研究Jon Bentley的Programming Pearls。

下面是您的代码的测试工具，非常受Programming Pearls启发，还有一个代码版本。我做的唯一更改是在二进制搜索中添加（现在注释掉的）调试打印。从测试代码的输出几乎是完美的（线束说的一切经过，但它是不完全正确）：

N = 0: 
search for 0 in 0 entries - returned 0 found 0 PASS 
N = 1: [0] = 1; 
search for 0 in 1 entries - returned -1   PASS 
search for 1 in 1 entries - returned 0 found 1 PASS 
search for 2 in 1 entries - returned -1   PASS 
N = 2: [0] = 1;[1] = 3; 
search for 0 in 2 entries - returned -1   PASS 
search for 1 in 2 entries - returned 0 found 1 PASS 
search for 2 in 2 entries - returned -1   PASS 
search for 3 in 2 entries - returned 1 found 3 PASS 
search for 4 in 2 entries - returned -1   PASS 
N = 3: [0] = 1;[1] = 3;[2] = 5; 
search for 0 in 3 entries - returned -1   PASS 
search for 1 in 3 entries - returned 0 found 1 PASS 
search for 2 in 3 entries - returned -1   PASS 
search for 3 in 3 entries - returned 1 found 3 PASS 
search for 4 in 3 entries - returned -1   PASS 
search for 5 in 3 entries - returned 2 found 5 PASS 
search for 6 in 3 entries - returned -1   PASS 
N = 4: [0] = 1;[1] = 3;[2] = 5;[3] = 7; 
search for 0 in 4 entries - returned -1   PASS 
search for 1 in 4 entries - returned 0 found 1 PASS 
search for 2 in 4 entries - returned -1   PASS 
search for 3 in 4 entries - returned 1 found 3 PASS 
search for 4 in 4 entries - returned -1   PASS 
search for 5 in 4 entries - returned 2 found 5 PASS 
search for 6 in 4 entries - returned -1   PASS 
search for 7 in 4 entries - returned 3 found 7 PASS 
search for 8 in 4 entries - returned -1   PASS 
N = 5: [0] = 1;[1] = 3;[2] = 5;[3] = 7;[4] = 9; 
search for 0 in 5 entries - returned -1   PASS 
search for 1 in 5 entries - returned 0 found 1 PASS 
search for 2 in 5 entries - returned -1   PASS 
search for 3 in 5 entries - returned 1 found 3 PASS 
search for 4 in 5 entries - returned -1   PASS 
search for 5 in 5 entries - returned 2 found 5 PASS 
search for 6 in 5 entries - returned -1   PASS 
search for 7 in 5 entries - returned 3 found 7 PASS 
search for 8 in 5 entries - returned -1   PASS 
search for 9 in 5 entries - returned 4 found 9 PASS 
search for 10 in 5 entries - returned -1   PASS 
N = 6: [0] = 1;[1] = 3;[2] = 5;[3] = 7;[4] = 9;[5] = 11; 
search for 0 in 6 entries - returned -1   PASS 
search for 1 in 6 entries - returned 0 found 1 PASS 
search for 2 in 6 entries - returned -1   PASS 
search for 3 in 6 entries - returned 1 found 3 PASS 
search for 4 in 6 entries - returned -1   PASS 
search for 5 in 6 entries - returned 2 found 5 PASS 
search for 6 in 6 entries - returned -1   PASS 
search for 7 in 6 entries - returned 3 found 7 PASS 
search for 8 in 6 entries - returned -1   PASS 
search for 9 in 6 entries - returned 4 found 9 PASS 
search for 10 in 6 entries - returned -1   PASS 
search for 11 in 6 entries - returned 5 found 11 PASS 
search for 12 in 6 entries - returned -1   PASS 
N = 7: [0] = 1;[1] = 3;[2] = 5;[3] = 7;[4] = 9;[5] = 11;[6] = 13; 
search for 0 in 7 entries - returned -1   PASS 
search for 1 in 7 entries - returned 0 found 1 PASS 
search for 2 in 7 entries - returned -1   PASS 
search for 3 in 7 entries - returned 1 found 3 PASS 
search for 4 in 7 entries - returned -1   PASS 
search for 5 in 7 entries - returned 2 found 5 PASS 
search for 6 in 7 entries - returned -1   PASS 
search for 7 in 7 entries - returned 3 found 7 PASS 
search for 8 in 7 entries - returned -1   PASS 
search for 9 in 7 entries - returned 4 found 9 PASS 
search for 10 in 7 entries - returned -1   PASS 
search for 11 in 7 entries - returned 5 found 11 PASS 
search for 12 in 7 entries - returned -1   PASS 
search for 13 in 7 entries - returned 6 found 13 PASS 
search for 14 in 7 entries - returned -1   PASS 
N = 8: [0] = 1;[1] = 3;[2] = 5;[3] = 7;[4] = 9;[5] = 11;[6] = 13;[7] = 15; 
search for 0 in 8 entries - returned -1   PASS 
search for 1 in 8 entries - returned 0 found 1 PASS 
search for 2 in 8 entries - returned -1   PASS 
search for 3 in 8 entries - returned 1 found 3 PASS 
search for 4 in 8 entries - returned -1   PASS 
search for 5 in 8 entries - returned 2 found 5 PASS 
search for 6 in 8 entries - returned -1   PASS 
search for 7 in 8 entries - returned 3 found 7 PASS 
search for 8 in 8 entries - returned -1   PASS 
search for 9 in 8 entries - returned 4 found 9 PASS 
search for 10 in 8 entries - returned -1   PASS 
search for 11 in 8 entries - returned 5 found 11 PASS 
search for 12 in 8 entries - returned -1   PASS 
search for 13 in 8 entries - returned 6 found 13 PASS 
search for 14 in 8 entries - returned -1   PASS 
search for 15 in 8 entries - returned 7 found 15 PASS 
search for 16 in 8 entries - returned -1   PASS 
N = 9: [0] = 1;[1] = 3;[2] = 5;[3] = 7;[4] = 9;[5] = 11;[6] = 13;[7] = 15;[8] = 17; 
search for 0 in 9 entries - returned -1   PASS 
search for 1 in 9 entries - returned 0 found 1 PASS 
search for 2 in 9 entries - returned -1   PASS 
search for 3 in 9 entries - returned 1 found 3 PASS 
search for 4 in 9 entries - returned -1   PASS 
search for 5 in 9 entries - returned 2 found 5 PASS 
search for 6 in 9 entries - returned -1   PASS 
search for 7 in 9 entries - returned 3 found 7 PASS 
search for 8 in 9 entries - returned -1   PASS 
search for 9 in 9 entries - returned 4 found 9 PASS 
search for 10 in 9 entries - returned -1   PASS 
search for 11 in 9 entries - returned 5 found 11 PASS 
search for 12 in 9 entries - returned -1   PASS 
search for 13 in 9 entries - returned 6 found 13 PASS 
search for 14 in 9 entries - returned -1   PASS 
search for 15 in 9 entries - returned 7 found 15 PASS 
search for 16 in 9 entries - returned -1   PASS 
search for 17 in 9 entries - returned 8 found 17 PASS 
search for 18 in 9 entries - returned -1   PASS

几乎所有的是罚款;唯一的问题是最初的搜索，它应该失败，因为在空数组中没有值。

测试代码是：

#include <stdio.h> 

int recurbinarysearch(int *oringalary, int low, int high, int target) 
{ 
    //printf("-->> %d..%d: ", low, high); 
    if (low > high) 
    { 
     //printf("<<-- %d ", -1); 
     return -1; 
    } 
    else 
    { 
     int mid = (low + high)/2; 
     if (target == * (oringalary + mid)) 
     { 
      //printf("<<-- %d ", mid); 
      return mid; 
     } 
     if (target > * (oringalary + mid)) 
     { 
      int r = recurbinarysearch(oringalary, mid + 1, high, target); 
      //printf("<<-- %d ", r); 
      return r; 
     } 
     if (target < * (oringalary + mid)) 
     { 
      int r = recurbinarysearch(oringalary, low, mid - 1, target); 
      //printf("<<-- %d ", r); 
      return r; 
     } 
    } 
} 

int main(void) 
{ 
    for (int i = 0; i < 10; i++) 
    { 
     int a[i+1]; // No zero-size arrays in C 
     printf("N = %2d: ", i); 
     for (int j = 0; j < i; j++) 
     { 
      a[j] = 2 * j + 1; 
      printf("[%d] = %d;",j, a[j]); 
     } 
     putchar('\n'); 

     for (int j = 0; j < 2*i+1; j++) 
     { 
      int f = recurbinarysearch(a, 0, i, j); 
      //putchar('\n'); // debug 
      printf("search for %2d in %2d entries - returned %2d", 
        j, i, f); 
      if (f >= 0 && f <= i) 
      { 
       printf(" found %2d", a[f]); 
       printf(" %s", (a[f] == j) ? "PASS" : "FAIL"); 
      } 
      else 
       printf(" %8s %s", "", (j % 2 == 0) ? "PASS" : "FAIL"); 
      putchar('\n'); 
     } 
    } 
    return(0); 
}

我要离开你的工作如何应对空数组情况。

来源

2013-02-19 06:31:05

相关问题

 相关问题