二分查找元素求比较次数_二分查找的比较次数怎么算的

在顺序表 { 12、15、17、20、24、30、38、43、45、51、52} 中，用二分法查找关键码 20需做（ ） 次关键字比较。
解：
数值    12    15    17    20    24    30    38    43    45    51    52
下标    0    1    2    3    4    5    6    7    8    9    10
以上一共11个数，按下标则是0…10，以下按照步骤进行

1、mid=（left + right）/ 2 = (0 + 10) / 2 = 5
即第一次使用目标值20与下标为5的值30进行比较，20<30，则 right = mid - 1 = 4；

2、mid=（left + right）/ 2 = (0 + 4) / 2 = 2
即第二次使用目标值20与下标为2的值17进行比较，20>17，则 left = mid + 1 = 3；

3、mid=（left + right）/ 2 = (3 + 4) / 2 = 3，（int，向下取整）
即第三次使用目标值20与下标为3的值20进行比较，20=20，返回下标3，算法结束。

综上所述，进行了3次比较.

注意：
1、每次二分时 mid=（left + right）/ 2 都是向下取整的；
2、每次比较后，如果没找到，就放弃当前比较的值，right = mid - 1 / left = mid + 1。
最后附上相关代码：
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {12, 15, 17, 20, 24, 30, 38, 43, 45, 51, 52};
        System.out.println(BinarySearch.search(arr, 20));
    }

    public static int search(int[] arr, int key) {
        int resIndex = -1;
        int left = 0;
        int right = arr.length - 1;

        while(left <= right) {
            int mid = (left + right) / 2;
            if (key == arr[mid]) {
                resIndex = mid;
                break;
            } else if (key < arr[mid]) {
                right = mid - 1;
            } else if (key > arr[mid]) {
                left = mid + 1;
            }
        }

        return resIndex;
    }
}
————————————————
版权声明：本文为CSDN博主「Shumao_94」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/u010992313/article/details/89373480