如何在 C++ 中为二进制搜索设置一个计数器？

Question

我不确定如何使用二进制搜索计数器来确定在找到输入的目标数字之前进行了多少次比较。我是否在接近二分查找末尾的位置添加一个计数器？

void search (int arr[])
{
int target;

int first = 0,
    last = MAX - 1,
    mid,
    position = -1;
int row = 2;
    bool found = false;

cout << "Enter in target number to search for: ";
cin >> target;

while (!found && first <= last)
{
    mid = (first + last) / 2;
    if (avg[row][mid] == target)
    {
        cout << "found at index " << mid << endl;
        found = true;
    }
    else if (avg[row][mid] > target)
        last = mid - 1;
    else
        first = mid + 1;
}
if (!found)
    cout << "Not found\n";
}

Answer 1

我会在 while 循环之前定义一个计数器变量，并在 while 循环结束时递增它，在最后一个 else 之后（不在 else 子句中）

Answer 2

int counter = 0;                  // Number of comparisons before target is found
while (!found && first <= last)
{
    mid = (first + last) / 2;
    counter = counter + 1;        // Changes to be made

    ... Rest of the code

    else
        first = mid + 1;
}

或

int counter = 0;                  // Number of comparison before target is found
while (!found && first <= last)
{
    mid = (first + last) / 2;

    if (avg[row][mid] == target)
    {
        cout << "found at index " << mid << endl;
        found = true;
        counter = counter + 1;
    }
    else if (avg[row][mid] > target) 
    {
        last = mid - 1;
        counter = counter + 1;      // Changes to be made
    }
    else 
    {
        first = mid + 1;
        counter = counter + 1;      // Changes to be made
    }    
}

这里在while循环之前声明了counter，然后每次加1，直到找到结果。

Answer 3

整数计数=0； ...其余代码 else if (avg[row][mid] > target) 最后 = 中间 - 1; 计数++

else
    first = mid + 1;
    count++;

} 如果（！发现） cout << "Not found\n"; cout<<"counter="<

如何在 C++ 中为二进制搜索设置一个计数器？

How to have a counter for a binary search in C++?

c++

counter

binary-search