溫馨提示×

C++二分查找函數(shù)怎樣確定中間值

c++
小樊
96
2024-07-21 02:44:57
欄目: 編程語言

在進(jìn)行二分查找時(shí)，確定中間值通常是通過計(jì)算左右邊界的平均值來得到的。具體步驟如下：

  1. 首先，確定要查找的數(shù)組范圍的左右邊界，通常分別用兩個(gè)指針left和right來表示。

  2. 計(jì)算中間值的下標(biāo)：mid = (left + right) / 2。

  3. 如果要查找的值等于數(shù)組中的中間值，則查找成功并返回中間值的下標(biāo)。

  4. 如果要查找的值小于中間值，則在左半部分繼續(xù)查找，更新右邊界為mid - 1；如果要查找的值大于中間值，則在右半部分繼續(xù)查找，更新左邊界為mid + 1。

  5. 重復(fù)步驟2-4，直到找到要查找的值或者左邊界大于右邊界時(shí)停止查找。

下面是一個(gè)示例C++函數(shù)，用于實(shí)現(xiàn)二分查找：

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; // 沒有找到目標(biāo)值
}

在這個(gè)函數(shù)中，我們通過計(jì)算(left + right) / 2來確定中間值的下標(biāo)mid，并在每次循環(huán)中更新左右邊界以繼續(xù)查找。

0 踩