折半查找法的步骤

1. 初始化：设数组的左边界为 left，右边界为 right，初始时 left = 0，right = n-1，其中 n 是数组的长度。
2. 查找过程：
   • 计算中间位置 mid = (left + right) / 2。
   • 比较中间元素 arr[mid] 与目标值 target：
     • 如果 arr[mid] == target，查找成功，返回 mid。
     • 如果 arr[mid] > target，说明目标值在左半部分，更新 right = mid - 1。
     • 如果 arr[mid] < target，说明目标值在右半部分，更新 left = mid + 1。
3. 重复：重复步骤2，直到 left > right，此时查找失败。

查找关键字为82的元素

有序表为 (1, 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 99)，查找关键字为82的元素。

1. 初始化：left = 0，right = 12。
2. 第一次比较：
   • mid = (0 + 12) / 2 = 6，arr[6] = 45。
   • 45 < 82，更新 left = 7。
3. 第二次比较：
   • mid = (7 + 12) / 2 = 9，arr[9] = 77。
   • 77 < 82，更新 left = 10。
4. 第三次比较：
   • mid = (10 + 12) / 2 = 11，arr[11] = 95。
   • 95 > 82，更新 right = 10。
5. 第四次比较：
   • mid = (10 + 10) / 2 = 10，arr[10] = 82。
   • 82 == 82，查找成功。

因此，查找关键字为82的元素需要4次比较。

折半查找左少右多