温馨提示×

C++二分查找函数怎样确定中间值

c++
小樊
104
2024-07-21 02:44:57
栏目: 编程语言

在进行二分查找时,确定中间值通常是通过计算左右边界的平均值来得到的。具体步骤如下:

  1. 首先,确定要查找的数组范围的左右边界,通常分别用两个指针leftright来表示。

  2. 计算中间值的下标:mid = (left + right) / 2

  3. 如果要查找的值等于数组中的中间值,则查找成功并返回中间值的下标。

  4. 如果要查找的值小于中间值,则在左半部分继续查找,更新右边界为mid - 1;如果要查找的值大于中间值,则在右半部分继续查找,更新左边界为mid + 1

  5. 重复步骤2-4,直到找到要查找的值或者左边界大于右边界时停止查找。

下面是一个示例C++函数,用于实现二分查找:

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1; // 没有找到目标值
}

在这个函数中,我们通过计算(left + right) / 2来确定中间值的下标mid,并在每次循环中更新左右边界以继续查找。

0