バイナリサーチは、ソートされた配列の値の変化を見つけるアルゴリズムと同じです。

Question

バイナリ検索に似ているようですが、例外はありますが のアルゴリズムを記述する必要があります。

問題： 整数の配列が与えられていると、値が変更されるインデックスを見つける必要があります。

仮定： あり、アレイ内の唯一の2つの値があるので、我々はたったの約 それは一度値を変更を心配する必要があります。 （例えば、使用0と100以下の実施例）

例（S）：

[0,0,0,0,100,100,100,100,100,100,100,100,100,100] //search would return 4 

[0,0,0,0,0,0,0,0,100,100,100,100,100,100] //search would return 8 

[0,0,0,0,0,0,0,0,0,0,0,0,0,100] //search would return 13 

説明：

ていない宿題の問題。私は、2週間にわたるアイテムの価格の変化に対応するソートされた配列 の日付を計算しなければならない問題があります。それらの日付の最後に価格 が異なる場合は、 価格が変更された正確な日を効率的に探したいと思います。

方法は、単にこれは、バイナリサーチのちょうど変化であるフォーマット

public int FindChangeIndex(int[] input){ 
    int changeIndex = -1 

    //use efficient binary-search 
    //like algorithm to find change index 

    return changeIndex;   
} 

Answer 1

にする必要がある、唯一のA及びB（！= B）

input = A, A, ...B,.. Bを含む配列を考えます

したがって、入力でBの最初の出現を見つけることです。

入力の中央がBに等しいと仮定すると、Bの最初の出現は前半にあり、逆もまた同様である。この検索は、検索スペースのサイズが空になるまで再帰的に行うことができます。

入力の長さをnとします。

int result = n - 1; 
int start = 0; 
int end = n - 1; 
while(start <= end){ 
    int mid = (start + end)/2; 
    if(input[mid] == B){ 
     result = mid; 
     end = mid - 1; 
    }else{ 
     start = mid + 1; 
    } 
} 
return result;