結論
ソート済みの配列限定ではあるが，少ない計算量で値の有無を確認できる探索アルゴリズム
内容
前提条件
- sort済みの配列であること
計算量
- O(longN)
key = \\求めたい値
dp = []\\ソート済みの配列
right = len(dp)-1
left = 0
while(right>=left)
{
mid = left+ (right-left)/2 \\これは原点からrightの半分大きくなった長さ
if(dp[mid]==key)return mid
elif(dp[mid] > key)return right = mid -1
\\左側に求める値があると推定
elif(dp[mid] < key)return left = mid + 1
\\右側に求める値があると推定
}
このコードの中でelifの部分で中央の要素番目を示す値に1という最小の変化を加えることにより，２文探索を行う範囲を決定している.
解釈
配列の中央の値をleft, rightのどちらかに設定するかで範囲を決めて数値を求めるアルゴリズム.