c++ 如何计算在二进制搜索中查找一个值所需的比较次数?

jv4diomz  于 2023-03-05  发布在  其他
关注(0)|答案(1)|浏览(85)

我正在做线性搜索,选择排序和二进制排序。我需要计数在二进制搜索中找到一个值所需要的比较次数,但我不知道在哪里正确地放置计数,目前我总是得到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;

    }
gojuced7

gojuced71#

要正确更新count变量,可以在while循环中每次将搜索值与数组中的元素进行比较时递增该变量。以下是binarySearch函数的更新实现:

int binarySearch(int arr[], int left, int right, int value, int& count)
    {
        while (left <= right)
        {
            count++;
            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;
    }

相关问题