二进制搜索最后一个元素搜索

Question

我正在学习二进制搜索，当我搜索数组中的最后一个元素时，搜索在循环中的一次迭代中完成

#include <stdio.h>
void binSearch(int arr[], int element, int size) {
int low = 0, mid, high = size - 1, i = 0;
while (low <= high) {
mid = (low + high) / 2;
if (arr[mid] == element) {
printf("The element was found after : %d", i);
// return mid;
}
if (arr[mid] < element) {
low = mid + 1;
} else {
high = mid - 1;
}
i++;
}
}
int main() {
int arr[20] = { 10, 22, 28, 33, 78, 124, 410, 511, 512, 999 };
int element = 999, size = sizeof(arr) / sizeof(int);
binSearch(arr, element, size);
return 0;
}

Answer 1

定义int arr[20] = { 10, 22, 28, 33, 78, 124, 410, 511, 512, 999 };定义了一个长度为20个元素的数组arr，其中只有10个元素被初始化。其余元素设置为0，这意味着数组是而不是排序的。

当调用binSearch(arr, 999, 20);时，循环中测试的第一个元素在mid = 19 / 2，而arr[9]实际上是999，所以the element was found after : 0迭代。

计算数组长度的表达式是正确的，尽管int size = sizeof(arr) / sizeof(*arr)更可靠，因为它不依赖于arr的元素类型。您应该让编译器通过将arr定义为：来确定实际长度

int arr[] = { 10, 22, 28, 33, 78, 124, 410, 511, 512, 999 };

这是一个修改版本：

#include <stdio.h>
int binSearch(int arr[], int element, int size) {
int low = 0, mid, high = size - 1, i = 0;
while (low <= high) {
mid = low + (high - low) / 2;
if (arr[mid] == element) {
printf("The element was found after : %dn", i);
return mid;
}
if (arr[mid] < element) {
low = mid + 1;
} else {
high = mid - 1;
}
i++;
}
return -1;
}
int main() {
int arr[] = { 10, 22, 28, 33, 78, 124, 410, 511, 512, 999 };
int element = 999, size = sizeof(arr) / sizeof(*arr);
binSearch(arr, element, size);
return 0;
}

Answer 2

您的代码中有一个错误。你只通过十个元素，但说你会通过二十个。在这种情况下，sizeof()告诉20，而不是10。

因此，检查的第一个元素是第十个，这恰好是你搜索的元素(999(。

试用：

int arr[] = {...}; // The number of elements is auto-calculated