在顺序表 { 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 {
二连浩特
发生一起中毒事故致4死
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;
}
遗传学三大定律}
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议