JAvaにおける二分法検索
717 ワード
1時間の複雑さ
二分法で探す時間の複雑度T(n)=T(n/2)+O(1)だからT(n)=O(logn)のすべての最悪の情況はlognで、最も良い情況はO(1)です.
2コード実装
//二分法検索
3コード分析
検索する値のサイズが配列の最大値と最小値の間にあるが、存在しない場合がある.この時は死の循環に入る.例えば配列は[1,3,7,9,10],numは4であり,sart=3,end=7,array[temp]=5にループし,num>array[temp]は常に実行される.この場合、-1.つまりstart=end-1を直接返すと、ターゲット値が見つかりません.
二分法で探す時間の複雑度T(n)=T(n/2)+O(1)だからT(n)=O(logn)のすべての最悪の情況はlognで、最も良い情況はO(1)です.
2コード実装
//二分法検索
private int binarySearchRank(int num, int[] array) {
int result = -1;
int start = 0;
int end = array.length-1;
while (startnum){
end = middle;
}else if(array[middle] 3コード分析
検索する値のサイズが配列の最大値と最小値の間にあるが、存在しない場合がある.この時は死の循環に入る.例えば配列は[1,3,7,9,10],numは4であり,sart=3,end=7,array[temp]=5にループし,num>array[temp]は常に実行される.この場合、-1.つまりstart=end-1を直接返すと、ターゲット値が見つかりません.