Binärsuchalgorithmus mit Intervall

Question

Ich versuche, meinen Code zu ändern, anstatt einen bestimmten Wert des Arrays zu finden, wird es den Wert eines Intervalls ausgeben, wenn es gefunden wird, Beispiel ist 60-70. Jede Hilfe wird geschätzt.

def binary (array, value): 

    while len(array)!= 0: 
     mid = len(array) // 2 

     if value == array[mid]:   
      return value 
     elif value > array[mid]:  
      array = array[mid+1:] 
     elif value < array [mid]:   
      array = array[0:mid] 

sequence = [1,2,5,9,13,42,69,123,256] 

print("found", binary(sequence,70)) 

Ich habe dies so weit und wollen, dass es einen bestimmten Intervall zu finden, also wenn ich 60-70 angeben wird es finden, was dazwischen ist.

Answer 1

Tatsächlich ist dies recht einfach:
Während für die Elemente in dem Intervall der Suche (lower, upper), eine binäre Suche auf den Array durchzuführen arr für den Index des kleinsten Elements arr[n], so dass arr[n] >= lower und der Index des größten Elements arr[m] , so dass arr[m] <= upper.

Nun gibt es mehrere Möglichkeiten:

• n < m: Es existieren mehrere Lösungen im Array. All das sind im Subarray bei Index n bis Index beginnend m einschließend
• n = m: gibt es genau eine Lösung: arr[n]
• n> m: keine Lösungen

für Werte Searching jenseits existieren eine bestimmte Schwelle kann mit binäre Suche wie folgt erfolgen:

def lowestGreaterThan(arr, threshold): 
    low = 0 
    high = len(arr) 

    while low < high: 
     mid = math.floor((low + high)/2) 

     print("low = ", low, " mid = ", mid, " high = ", high) 

     if arr[mid] == threshold: 
      return mid 
     elif arr[mid] < threshold and mid != low: 
      low = mid 
     elif arr[mid] > threshold and mid != high: 
      high = mid 
     else: 
      # terminate with index pointing to the first element greater than low 
      high = low = low + 1 

    return low 

Leider Kampf das Aussehen des Codes, meine python bei weitem nicht perfekt. Wie auch immer, dies sollte die Grundidee des Ansatzes zeigen. Der Algorithmus sucht grundsätzlich nach dem Index ind des ersten Elements im Array mit der Eigenschaft arr[ind] >= threshold.