Recherche binaire pour l'index le plus bas d'un élément

Question

Je veux implémenter une fonction de recherche binaire qui retourne l'index le plus bas de l'élément à rechercher. Voici mon code:

def binarySearch(arr,x): 
    n=len(arr) 
    if n==1: 
     if arr[0]==x: 
      return 0 
     else: 
      return -1 # not in list 
    else: 
     m=int(n/2) 
     if x <= arr[m]: 
      return binarySearch(arr[:m],x) 
     else: 
      return m+binarySearch(arr[m+1:],x) 

Cependant, cela ne fonctionne pas correctement. Est-ce que quelqu'un peut m'aider?

Answer 1

Vous trouverez l'index de un élément qui est égal à x en ajoutant simplement un test pour l'égalité dans la else partie de votre fonction:

def binarySearch(arr,x): 
    n=len(arr) 
    if n==1: 
     if arr[0]==x: 
      return 0 
     else: 
      return -1 # not in list 
    else: 
     m = int(n/2) 
     if x < arr[m]: 
      return binarySearch(arr[:m],x) 
     elif x == arr[m]: 
      return m 
     else: 
      return m + binarySearch(arr[m+1:],x) 

Cela empêche le problème de récursion passé la solution , mentionné par @Fruitpunchsalami

Cependant, cela ne vous donnera pas l'indice le plus bas :

>>> binarySearch([1,2,3,3,4,4], 3) 
3 

Voici la bonne réponse serait 2.

Un autre problème est la manipulation des éléments qui ne se trouvent pas, en raison du cas particulier de -1. Nous obtenons:

>>> binarySearch([1,2,3,3,6,6], 4) 
2 

Je serais tenté de proposer une solution générique dans laquelle vous trouverez l'index de l'élément le plus grand moins de x, puis vérifiez l'élément dans la position d'un haut de celle-ci. La recherche du plus grand élément inférieur à x peut être effectuée en temps logarithmique; vérifier l'élément à droite est constante de temps, vous obtenez toujours O (log n):

def binarySearch(arr,x): 
    '''Returns the lowest index of the element equal to `x` or NaN if not found.''' 
    def innerBinarySearch(arr, x): 
     '''Find index of largest element strictly less than `x`.''' 
     if len(arr) == 0: 
      return -1 
     m = len(arr) // 2 
     if x <= arr[m]: 
      return innerBinarySearch(arr[:m], x) 
     else: 
      return m + 1 + innerBinarySearch(arr[m + 1:], x) 

    idx = innerBinarySearch(arr,x) + 1 
    if 0 <= idx < len(arr) and arr[idx] == x: 
     return idx 
    return float('nan') 

Faites-en une seule fonction:

def binarySearch(arr,x): 
    '''Returns the lowest index of the element equal to `x` or NaN if not found.''' 
    if len(arr) == 0: 
     return float('nan') 
    m = len(arr) // 2 
    if arr[m] < x: 
     return m + 1 + binarySearch(arr[m + 1:], x) 
    elif x < arr[m] or (0 < m and arr[m-1] == x): 
     return binarySearch(arr[:m], x) 
    else: 
     return m 

Answer 2

def binarySearch(arr,x): 

    if len(arr) == 0: 
     return 0 

    else: 
     m=int(len(arr)/2) 

     if arr[m] == x: 
      c = 1 

      while arr[m-c] == x: 
       c += 1 
      return m-c+1 

     else: 
      if x < arr[m]: 
       return binarySearch(arr[:m],x) 
      else: 
       return binarySearch(arr[m+1:],x) 

Cela corrige vos problèmes tout en vous donnant l'indice le plus bas