我正在做线性搜索,选择排序和二进制排序。我需要计数在二进制搜索中找到一个值所需要的比较次数,但我不知道在哪里正确地放置计数,目前我总是得到0。
int binarySearch(int arr[], int left, int right, int value, int count)
{
count ++;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (arr[mid] == value)
{
return mid;
}
else if (arr[mid] < value)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return -1;
}
int main()
//binary search
// keep count of comparisons
int count = 0;
int binaryIndex = binarySearch(arr, 0, 19,value, count);
if (binaryIndex == -1)
{
cout << endl<< "Element cannot be found in the arry"<< endl;
}
else {
cout << endl << "Element is at index: " << binaryIndex;
cout << "# of comparisons " << count;
}
1条答案
按热度按时间gojuced71#
要正确更新count变量,可以在while循环中每次将搜索值与数组中的元素进行比较时递增该变量。以下是binarySearch函数的更新实现: