Dividim una col·lecció d'elements en dues meitats a la cerca binària per reduir el nombre de comparacions directes necessàries per descobrir un element. Tanmateix, hi ha un requisit: els elements de la matriu s'han d'ordenar prèviament.

Cerca binària

El Cerca binària El mètode localitza l'índex d'un determinat membre de la llista. Es troba entre els algorismes més populars i ràpids. Perquè funcioni el procediment de cerca binària, les entrades de la llista s'han d'ordenar.

cadena comparada

Cerca binària és una tècnica de cerca més eficient per localitzar l'índex d'un element que Cerca lineal ja que no hem d'examinar tots els índexs de llista.

Tota l'operació de l'algoritme de cerca binària es pot resumir en els passos següents:

• Localitzeu l'element central a la matriu ordenada.
• Feu una comparació entre l'element a localitzar i l'element central.
• Si aquest element és igual a l'element central de la llista donada, es retorna l'índex de l'element central. En cas contrari, l'algorisme compararà l'element amb l'element del mig.
• Ara, si l'element que cal localitzar és més gran que l'element central de la llista, es compararà amb la meitat dreta de la llista, és a dir, els elements després de l'índex central.
• O si l'element és inferior a l'element del centre de la llista, es compararà només amb la meitat esquerra de la llista, és a dir, elements anteriors a l'índex central.

Cerca binària recursiva

La cerca binària implica dividir contínuament l'interval de cerca en 2 parts iguals per descobrir un element en una matriu ordenada, i la cerca binària recurrent implica desglossar el procediment de cerca binària complet en problemes més petits. Una cerca binària recursiva és la resposta recursiva a una cerca binària.

Les següents són les característiques que han de complir les solucions totalment recursives:

1. Es requereix un cas base per a un enfocament recursiu.
2. Hi ha d'haver un cas de prova recursiu en un enfocament recursiu.
3. Un enfocament recursiu s'ha d'apropar al cas base.

La subdivisió més baixa d'un problema complicat està representada per un cas base, que és un cas final. Per tant, per dur a terme la cerca binària per mètode recursiu, el nostre algorisme ha de contenir un cas base i un cas recursiu, amb el cas recursiu progressant cap al cas base. En cas contrari, el procés no acabaria mai i donaria lloc a un bucle interminable.

La tècnica de cerca binària redueix el temps que triga a trobar un element específic dins d'una matriu ordenada. El mètode de cerca binària sovint s'implementa de manera iterativa, però també podem implementar-lo de forma recursiva descomposant-lo en peces més petites.

Codi

matriu dinàmica java

 #defining a function to execute Binary Search on any given sorted list L. #start is the lowest index of the list being checked at any given time. #end is the highest index of the list being checked at any given time. #item is the item to be searched in the list. def binary_search(L, start, end, item): if end >= start: middle = (start + end) // 2 if L[middle] == item: return middle #middle element is the item to be located #if middle item is greater than the item to be searched, left side of the list will be searched elif L[middle] > item: #starting index will be same but ending index will be the middle of the main list i.e. left half of the list is given in function. return binary_search(L, start, middle - 1, item) else: #if middle item is smaller than the item to be searched, new starting index will be middle of the list i.e. right half of the list. return binary_search(L, middle + 1, end, item) else: #if element is not present in the list return -1 #Drivers code my_list = [ 2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22 ] element_to_search = 6 print('The given list is') print(my_list) index_of_element = binary_search(my_list, 0, len(my_list)-1, element_to_search) if index_of_element != -1: print('Element searched is found at the index ', str(index_of_element), 'of given list') else: print('Element searched is not found in the given list!') 

Sortida:

 The given list is [2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22] Element searched is found at the index 2 of given list 

La recursivitat és una tècnica de programació i resolució de problemes extremadament potent. Podem utilitzar-lo per avaluar i executar una varietat d'algorismes, que van des de problemes iteratius simples fins a problemes complicats de retrocés. En aquest tutorial, hem analitzat l'ús del llenguatge Python per crear el mètode de cerca binària recursiva.