二分探索特集1-非減算配列でA[i]=iを満たすiを探す
1021 ワード
Javaeyeで二分検索に関する質問を見ましたhttp://www.iteye.com/topic/1118606簡潔で効率的なアルゴリズムを設計しました
題目:ひとつの非減衰の配列Aについて、A[i]=iが存在して、o(lgn)のアルゴリズムを求めてiを探し出して、
分析:
1,任意のjとiに対して、j>iであればA[j]>=A[i];
2、求める解がIであるA[I]=Iであると仮定すると、任意のjに対して、A[j]>jであればI2を使用して、次のアルゴリズムを得ることができます.
解析:
A[j]>jの場合は[j,end]の区間を捨て、A[j]ネットユーザーの指導を歓迎します.
題目:ひとつの非減衰の配列Aについて、A[i]=iが存在して、o(lgn)のアルゴリズムを求めてiを探し出して、
分析:
1,任意のjとiに対して、j>iであればA[j]>=A[i];
2、求める解がIであるA[I]=Iであると仮定すると、任意のjに対して、A[j]>jであればI
public static int search(int[] A) {
int len = A.length;
int start = 0;
int end = len;
while (start <= end) {
int j = (start + end) / 2;
if (A[j] == j) {
return j;
}
if (A[j] > j) {
end = j - 1;
} else if (A[j] < j) {
start = j + 1;
}
}
return -1;
}
解析:
A[j]>jの場合は[j,end]の区間を捨て、A[j]