PROGRAMA PYTHON PER A LA CERCA BINÀRIA (RECURSIVA I ITERATIVA)

En poques paraules, aquest algorisme de cerca aprofita una col·lecció d'elements que ja està ordenada ignorant la meitat dels elements després d'una sola comparació.

Compara x amb l'element central.
Si x coincideix amb l'element central, retornem l'índex mitjà.
En cas contrari, si x és més gran que l'element central, aleshores x només pot estar a la meitat subbarrada dreta (més) després de l'element mitjà. A continuació, tornem a aplicar l'algorisme per a la meitat dreta.
En cas contrari, si x és més petit, l'objectiu x ha d'estar a la meitat esquerra (inferior). Per tant, apliquem l'algorisme per a la meitat esquerra.

Programa Python per a la cerca binària amb recursiu

Python 3

# Python 3 program for recursive binary search.> # Modifications needed for the older Python 2 are found in comments.> # Returns index of x in arr if present, else -1> def> binary_search(arr, low, high, x):> > # Check base case> > if> high>> => low:> > mid> => (high> +> low)> /> /> 2> > # If element is present at the middle itself> > if> arr[mid]> => => x:> > return> mid> > # If element is smaller than mid, then it can only> > # be present in left subarray> > elif> arr[mid]>x:> > return> binary_search(arr, low, mid> -> 1> , x)> > # Else the element can only be present in right subarray> > else> :> > return> binary_search(arr, mid> +> 1> , high, x)> > else> :> > # Element is not present in the array> > return> -> 1> # Test array> arr> => [> 2> ,> 3> ,> 4> ,> 10> ,> 40> ]> x> => 10> # Function call> result> => binary_search(arr,> 0> ,> len> (arr)> -> 1> , x)> if> result !> => -> 1> :> > print> (> 'Element is present at index'> ,> str> (result))> else> :> > print> (> 'Element is not present in array'> )>

Sortida

Element is present at index 3

Complexitat temporal : O(log n)

Espai Auxiliar : O (inici de sessió) [NOTA: La recursivitat crea una pila de trucades]

Programa Python per a la cerca binària amb iterativa

Python 3

# Iterative Binary Search Function> # It returns index of x in given array arr if present,> # else returns -1> def> binary_search(arr, x):> > low> => 0> > high> => len> (arr)> -> 1> > mid> => 0> > while> low <> => high:> > mid> => (high> +> low)> /> /> 2> > # If x is greater, ignore left half> > if>

arr[mid]   low = mid + 1  # If x is smaller, ignore right half  elif arr[mid]>x: alt = mig - 1 # significa que x està present a mig else: return mid # Si arribem aquí, aleshores l'element no estava present return -1 # Matriu de prova arr = [ 2, 3, 4, 10, 40 ] x = 10 # Resultat de la trucada de funció = binary_search(arr, x) if result != -1: print('L'element és present a l'índex', str(resultat)) else: print('L'element no està present a la matriu ')>>>

>    
      
      Espai Auxiliar     : O(1)  
      Programa Python per a la cerca binària Utilitzant el mòdul de bisecte integrat     
      Enfocament pas a pas:     
     El codi importa el mòdul bisect que proporciona suport per a la cerca binària.  
   Es defineix la funció binary_search_bisect() que pren una matriu arr i l'element per cercar x com a entrades.  
   La funció crida a la funció bisect_left() del mòdul bisect que troba la posició de l'element a la matriu ordenada arr on s'ha d'inserir x per mantenir l'ordre ordenat. Si l'element ja està present a la matriu, aquesta funció retornarà la seva posició.  
   Aleshores, la funció comprova si l'índex retornat i es troba dins de l'interval de la matriu i si l'element d'aquest índex és igual a x.  
   Si la condició és certa, aleshores la funció retorna l'índex i com a posició de l'element a la matriu.  
   Si la condició és falsa, la funció retorna -1 indicant que l'element no està present a la matriu.  
   Aleshores, el codi defineix una matriu arr i un element x per cercar.  
   La funció binary_search_bisect() es crida amb arr i x com a entrades i el resultat retornat s'emmagatzema a la variable de resultat.  
   Aleshores, el codi comprova si el resultat no és igual a -1, indicant que l'element està present a la matriu. Si és cert, imprimeix la posició de l'element a la matriu.  
   Si el resultat és igual a -1, el codi imprimeix un missatge que indica que l'element no està present a la matriu.  
  
  Python 3 
      
       
   
       
       
     
     
   
          import>   bisect>   >   def>   binary_search_bisect(arr, x):>   >  i>  =>   bisect.bisect_left(arr, x)>   >  if>   i !>  =>   len>  (arr)>  and>   arr[i]>  =>  =>   x:>   >  return>   i>   >  else>  :>   >  return>   ->  1>   >   >   # Test array>   arr>  =>   [>  2>  ,>  3>  ,>  4>  ,>  10>  ,>  40>  ]>   x>  =>   10>   >   # Function call>   result>  =>   binary_search_bisect(arr, x)>   >   if>   result !>  =>   ->  1>  :>   >  print>  (>  'Element is present at index'>  ,>  str>  (result))>   else>  :>   >  print>  (>  'Element is not present in array'>  )>     
  
  
   
      
    
      
    
  Sortida    
  Element is present at index 3 
      Complexitat temporal     : O(log n)  
      Espai Auxiliar     : O(1)