二分検索アルゴリズムの時間的複雑さ
アルゴリズムの時間的複雑さはfor,whileなどに含まれる基本演算ユニットのサイクル数にほかならない.
1、二分検索
二分検索(binary search)は、折半検索(half-interval search)とも呼ばれ、半分に分けて次の検索を行うため、時間の複雑さはwhileサイクルの回数にほかならない.
2、時間複雑度
たとえば、合計n個の要素があり、検索するたびの区間サイズはn,n/2,n/4,...,n/2^k(次の操作要素の残りの数)であり、ここでkはループの回数である.n/2^kの整列後>=1,すなわちn/2^k=1としてk=log 2 n,(2をベースとしたnの対数)を得ることができるため,時間的複雑度はO()=O(logn)を表すことができる.
1、二分検索
二分検索(binary search)は、折半検索(half-interval search)とも呼ばれ、半分に分けて次の検索を行うため、時間の複雑さはwhileサイクルの回数にほかならない.
// Java
public static int binarySearch(Integer[] srcArray, int des) {
int low = 0;
int high = srcArray.length - 1;
while ((low <= high) && (low <= srcArray.length - 1)
&& (high <= srcArray.length - 1)) {
int middle = (high + low) >> 1;
if (des == srcArray[middle]) {
return middle;
} else if (des < srcArray[middle]) {
high = middle - 1;
} else {
low = middle + 1;
}
}
return -1;
}
2、時間複雑度
たとえば、合計n個の要素があり、検索するたびの区間サイズはn,n/2,n/4,...,n/2^k(次の操作要素の残りの数)であり、ここでkはループの回数である.n/2^kの整列後>=1,すなわちn/2^k=1としてk=log 2 n,(2をベースとしたnの対数)を得ることができるため,時間的複雑度はO()=O(logn)を表すことができる.