复杂性的计量 两种查找算法的效率比较 int search(int val){∥二分查找 int i,j,k; ,/int a m无重复且已按从小到大排序 i=0;j=m-1; while(i <j) k=i+(j-i)/2; if (val <a[k)j=k-1; if (val >a k)i=k+1; 3 if (j-i==-1)freturn 1;}else {return k;} }∥在最坏情况下，只需要把val与a的1og2m个 ∥分量比较，显然效率高于前一个算法复杂性的计量 • 两种查找算法的效率比较 int search(int val) { // 二分查找 int i, j, k; //int a[m]无重复且已按从小到大排序 i = 0; j = m −1; while(i <= j) { k = i + (j − i)/2; if (val <= a[k]) j = k − 1; if (val >= a[k]) i = k + 1; } if (j − i == − 1) {return − 1;} else {return k;} } // 在最坏情况下，只需要把val与a的log2 m个 // 分量比较，显然效率高于前一个算法 11