Dividimos uma coleção de itens em duas metades na Pesquisa Binária para diminuir o número de comparações diretas necessárias para descobrir um elemento. Entretanto, há um requisito: os itens do array devem ser classificados previamente.

Pesquisa binária

O Pesquisa binária O método localiza o índice de um determinado membro da lista. Está entre os algoritmos mais populares e rápidos. Para que o procedimento de Pesquisa Binária funcione, as entradas da lista devem ser classificadas.

tupla java

Pesquisa binária é uma técnica de pesquisa mais eficiente para localizar o índice de um elemento do que Pesquisa Linear já que não precisamos examinar todos os índices da lista.

Todo o funcionamento do Algoritmo de Pesquisa Binária pode ser resumido nas seguintes etapas:

• Localize o elemento do meio na matriz classificada.
• Faça uma comparação entre o elemento a ser localizado e o elemento intermediário.
• Se esse elemento for igual ao elemento do meio da lista fornecida, o índice do elemento do meio será retornado. Caso contrário, o algoritmo irá comparar o elemento com o item do meio.
• Agora, se o elemento a ser localizado for maior que o item do meio da lista, ele será comparado à metade direita da lista, ou seja, aos elementos posteriores ao índice do meio.
• Ou se o elemento for menor que o elemento no meio da lista, então ele será comparado apenas à metade esquerda da lista, ou seja, aos elementos antes do índice do meio.

Pesquisa binária recursiva

A pesquisa binária implica dividir continuamente o intervalo de pesquisa em duas partes iguais para descobrir um elemento em uma matriz classificada, e a pesquisa binária recorrente envolve dividir o procedimento completo de pesquisa binária em questões menores. Uma pesquisa binária recursiva é a resposta recursiva a uma pesquisa binária.

A seguir estão as características que as soluções totalmente recursivas devem atender:

1. Um caso base é necessário para uma abordagem recursiva.
2. Deve haver um caso de teste recursivo em uma abordagem recursiva.
3. Uma abordagem recursiva precisa se aproximar do caso base.

A subdivisão mais baixa de um problema complicado é representada por um caso base, que é um caso final. Assim, para realizar a Busca binária pelo método recursivo, nosso algoritmo deve conter um caso base e um caso recursivo, com o caso recursivo progredindo para o caso base. Caso contrário, o processo nunca terminaria e resultaria em um loop infinito.

A técnica de pesquisa binária reduz o tempo necessário para encontrar um elemento específico dentro de uma matriz classificada. O método de pesquisa binária é frequentemente implementado iterativamente, mas também podemos implementá-lo recursivamente, dividindo-o em partes menores.

Código

classe vs objeto em 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!') 

Saída:

 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 

A recursão é uma técnica de programação e resolução de problemas extremamente poderosa. Podemos usá-lo para avaliar e executar uma variedade de algoritmos, desde simples problemas iterativos até complicados problemas de retrocesso. Neste tutorial, vimos como usar a linguagem Python para criar o método de pesquisa binária recursiva.