moncerically増加してからsequenceceraを減らす数を見つける

Question

monotonically増加するシーケンスの最大値または最小値を見つけることは、O（log n）で実行できます。

しかし、このようなシーケンスに数値が存在するかどうかを確認したい場合は、これもO（log n）で行うことができますか？

私はそれが可能ではないと思います。この例を考えてみましょう：1 4 5 6 7 10 8 3 2 0

この例では、シーケンスに '2'が含まれているかどうかを調べる必要がある場合、検索スペースを半分に分割する条件はありません元の検索スペース最悪の場合は、O（n）になります.2つの検索を行うときに、両方の半分を確認する必要があります。

この検索がO n）時間？

Answer 1

あなたが注目したように、最大​​値（およびその位置）はO（logn）にあります。次に、O（logn）である各部分でバイナリ検索を行うことができます。

上記の例では、位置5で最大10を見つけることができます。 次に、[0..5]（1,4,5,6,7,10）の部分配列でバイナリ検索を行います。 2が見つからない場合は、他の部分（10、8、3、2、0）でバイナリ検索を実行します。

O（logn）で最大値を見つけるには：中央の2つの要素を調べます：7 < 10.これで、シーケンスの右半分で最大値を探す必要があります。 （10,8,3,2,0）である。 8と3を見て、左側の部分（10、8）に進みます。

Answer 2

私が覚えているように、要素が増加してから減少する順序の配列の最適な検索は、フィボナッチ検索アルゴリズムです。

Answer 3

ここはpythonのスケッチです。要するに、増加領域と減少領域に隣接する要素を見つけることを目指しています（これは、隣接要素をチェックする2つの条件を確認します）。そして、この要素が見つかるまで、標準バイナリ検索のようにホッピングします。希望が役立ちます。

def get_max(arr): 
    if len(arr) == 1: 
     return arr[0] 
    if len(arr) in [0,2]: 
     return None 
    left, right = 0, len(arr) - 1 
    while left <= right: 
     mid = (left+right) // 2 
     #increasing region 
     if arr[mid+1] > arr[mid] and arr[mid] > arr[mid-1]: 
      left = mid + 1 
     #decreasing region 
     elif arr[mid+1] < arr[mid] and arr[mid] < arr[mid-1]: 
      right = mid - 1 
     elif arr[mid+1] < arr[mid] and arr[mid-1] > arr[mid]: 
      return arr[mid-1] 
     else: 
      return arr[mid] 
    return -1