[アルゴリズム]3週目2回目の運転時
3854 ワード
Chap01. Analyzing Algorithms and Promblems: Principles and Examples
Searching an Ordered Array
Let's Devide-and-Conquer!
Strategy D
バイナリサーチ
Algorithm D : Binary Search
int binarySearch(int[] E, int first, int last, int K)
if (last < first)
index = -1;
else
int mid = (first + last)/2 /* 내림 */
if (K == E[mid])
index = mid;
else if (K < E[mid])
index = binarySearch(E, first, mid-1, K)
else
index = binarySearch(E, mid+1, last, K);
return indexAnalysis D
basic operation:Kとarry内entry間の比較演算
">、<、=="を1回の比較と見なす
d<=lg(n)は、再帰関数に入る前に1回比較し、再帰関数比較底関数logn
2 n+1例では、
等比数列の和を用いたS d定理次に仮定[2]を用いてnについて整理する
Reference
この問題について([アルゴリズム]3週目2回目の運転時), 我々は、より多くの情報をここで見つけました https://velog.io/@dkswlgus00/알고리즘-3주차-2차시テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol