在進行二分查找時,確定中間值通常是通過計算左右邊界的平均值來得到的。具體步驟如下:
首先,確定要查找的數組范圍的左右邊界,通常分別用兩個指針left
和right
來表示。
計算中間值的下標:mid = (left + right) / 2
。
如果要查找的值等于數組中的中間值,則查找成功并返回中間值的下標。
如果要查找的值小于中間值,則在左半部分繼續查找,更新右邊界為mid - 1
;如果要查找的值大于中間值,則在右半部分繼續查找,更新左邊界為mid + 1
。
重復步驟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
,并在每次循環中更新左右邊界以繼續查找。