如何在C中简化这个有效的二进制搜索代码?

几个星期前,嘿家伙们开始在C语言中学习algothiritms,只是想知道如何让我的代码更简单,它只是一个二元搜索function。 但唯一的问题是你必须保持论点相同,提前谢谢。

bool search(int value, int values[], int n) { int min = values[0]; int max = values[n-1]; int average = (min + max) / 2; if(average == value) { return true; } while (average > value) { max = average - 1; average = (min + max) / 2; } while (average < value) { min = average + 1; average = (min + max) / 2; } if (max < min) { return false; } if (average == value) { printf("%i\n", average); return true; } else { return false; } } 

这不是二进制搜索的正确实现,所有条件必须在一个循环中,例如:max也必须是n-1而不是值[n-1]和min = 0而不是值[0],你也应该将值[average]与值进行比较而不仅仅是平均变量。

  bool search(int value, int values[], int n){ int min = 0; int max = n-1; int average ; while(max>=min){ average = (min + max) / 2; if(values[average] == value) { return true; } if (values[average] > value) { max = average - 1; average = (min + max) / 2; } if (values[average] < value) { min = average + 1; average = (min + max) / 2; } } return false; } 

在二进制搜索中你需要做一些小事:处理长度= 0的情况,确保你测试的位置始终有效,确保你没有溢出(即`(低+高) / 2’不是最好的写法),确保新的测试位置总是与前一个测试位置不同,等等。

在完成了一百万次之后,我编写的每个二进制搜索现在都是这样完成的:

 bool search(int[] array, int length, int valueToFind) { int pos=0; int limit=length; while(pos>1); if (array[testpos] 

请注意,我们只需要在每次迭代时进行一次比较,这比大多数可以执行的实现要快2.我们可以在每次只使用一次比较时,可靠地找到要查找的元素所在的位置。迭代,然后在最后测试,看看我们想要的元素是否存在。

我们计算testpos的方式确保pos <= testpos < limit ,即使length是最大可能的整数值,它也能工作。

这种forms还可以很容易地读出你想要看到的不变量,而不必考虑像high这样的奇怪边界条件。 当你走出循环时, pos==limit所以你不必担心使用错误的等等。

这个循环中的条件也很容易适应不同目的的二进制搜索,例如“找到插入x的位置,确保它在已经在数组中的所有x之后”,“找到数组中的第一个 x”,“找到数组中的最后一个 x“,等等。