若有序列{2,5,6,10,15,21,26,30,56,78},若用折半查找法赵30,则需要比几次

Question

若有序列{2,5,6,10,15,21,26,30,56,78},若用折半查找法赵30,则需要比
几次

Answer 1

a[10] = {2,5,6,10,15,21,26,30,56,78}
第一次,比较 a[(0+9)/2] == 30 =>a[4] = 15 < 30 ；
第二次,比较 a[(4+1+9)/2] == 30 => a[7] = 30 == 30 ,所以第二次就可以找到了；
折半法就是先用下标是 i = (0+n)/2 的值(相当于首+尾的和除二)与需要查找的数x相比(n是数组的最大下标,例子里面是9),
如果 x < a[i] ,就用下标是 i = (0+i-1)/2 的值(相当于首+(i-1)的和除二)与需要查找的数x相比；
如果 x == a[i] ,下标 i 就是需要找的那个数的下标了；
如果 x > a[i] ,就用下标是 i = (i+1+9)/2 的值(相当于(i+1)+尾的和除二)与需要查找的数x相比；
以此类推.直到 x == a[i] ,或者是首>尾的时候就结束了.