Um método rápido para localizar um elemento específico em uma matriz classificada é uma pesquisa binária. A tarefa inicial deste algoritmo é comparar o valor alvo com o elemento intermediário do array. A pesquisa é considerada bem-sucedida se o valor alvo estiver contido no elemento intermediário. O algoritmo procurará na metade esquerda da matriz se o valor da meta for menor que o elemento central. O programa examinará a metade direita da matriz se o valor da meta for maior que o elemento central. Este método é repetido até que o valor da meta ou o intervalo de pesquisa se esgote.
definido em java
Uso:
Bancos de dados, mecanismos de busca e processamento de dados são apenas alguns dos aplicativos que utilizam a estratégia de busca binária.
Características:
- A matriz de valores de entrada deve ser classificada.
- A cada iteração, o método reduz o intervalo de pesquisa pela metade, tornando-o particularmente eficiente para grandes conjuntos de dados.
- O algoritmo tem uma complexidade de tempo de pior caso O (log n).
- Encontrar o valor desejado é feito pelo programa usando uma estratégia de dividir e conquistar.
Aqui está um exemplo direto do algoritmo de pesquisa binária escrito em C:
#include int binary_search(int arr[], int left, int right, int target) { while (left <= right) { int mid="left" + (right - left) 2; if (arr[mid]="=" target) return mid; } else < left="mid" 1; right="mid" -1; target not found main() arr[]="{1," 3, 5, 7, 9}; n="sizeof(arr)" sizeof(arr[0]); index="binary_search(arr," 0, 1, target); (index="=" -1) printf('target found
'); at %d
', index); 0; pre> <p> <strong>Output:</strong> </p> <pre> Target found at index 2 </pre> <ul> <li>The binary_search function accepts four arguments: the array to search, the left and right search range boundaries, and the target value to look for. The function returns its index if the desired value can be found; else, it returns -1.</li> <li>The main function creates an array arr and a value target. The binary_search function is then used to search the array for the desired value. The function returns the index where the target value was located if it was, the function returns the index at which it was found. Otherwise, the message 'Target not found' is displayed.</li> <li>The binary search algorithm's implementation is basic. We begin by setting the left border to the array's initial index and the right boundary to the array's last index. Once the left boundary is less than or equal to the right border, the array is looped through one more time. We use the formula (left + right) / 2 within the loop to calculate the middle index of the search range. This formula computes the integer value of the middle index's floor.</li> <li>The centre member of the array is contrasted with the target value. We return the index of the middle element if they are equal. We change the right boundary to be one less than the middle index if the desired value is less than the middle element. If not, we adjust the left border so that it is one more than the centre index. We continue doing this until the goal value is obtained or the search space is filled.</li> <li>The temporal complexity of the binary search algorithm, where n is the array size, is O(log n). This is far more efficient than linear search, which has a temporal complexity of O(n), where n is the size of the array.</li> <li>Finally, the binary search technique offers a useful way to locate a particular member in a sorted array. It is easy to build and has an O(log n) time complexity, making it an efficient approach for large datasets.</li> </ul> <h3>Advantages:</h3> <ul> <li>For large datasets, the binary search algorithm is exceptionally efficient, and it is capable of handling a wide range of input sizes.</li> <li>The algorithm is simple to implement in almost all programming languages.</li> </ul> <h3>Disadvantages:</h3> <ul> <li>Before using the binary search technique, the input array must be sorted, which takes more time and memory.</li> <li>The algorithm cannot be applied to unsorted arrays.</li> <li>The algorithm may yield inaccurate results if the input array is not sorted.</li> <li>The binary search algorithm is not appropriate for tiny datasets since the technique's overhead may outweigh its benefits.</li> </ul> <h2>Conclusion:</h2> <p>A sorted array can be quickly searched for a specific element using the binary search technique. It employs a divide-and-conquer strategy to cut the search range in half with each iteration, allowing it to be highly efficient for large datasets. However, before using the binary search technique, the input array must be sorted, which takes extra time and memory. The binary search algorithm is a sophisticated data processing tool that is widely utilised in various sectors.</p> <hr></=> - A função binary_search aceita quatro argumentos: o array a ser pesquisado, os limites esquerdo e direito do intervalo de pesquisa e o valor alvo a ser procurado. A função retorna seu índice se o valor desejado puder ser encontrado; caso contrário, ele retorna -1.
- A função principal cria um array arr e um valor alvo. A função binary_search é então usada para pesquisar no array o valor desejado. A função retorna o índice onde o valor alvo estava localizado, se estivesse, a função retorna o índice em que foi encontrado. Caso contrário, será exibida a mensagem 'Destino não encontrado'.
- A implementação do algoritmo de busca binária é básica. Começamos definindo a borda esquerda para o índice inicial do array e a borda direita para o último índice do array. Quando o limite esquerdo for menor ou igual ao limite direito, a matriz será repetida mais uma vez. Usamos a fórmula (esquerda + direita) / 2 dentro do loop para calcular o índice intermediário do intervalo de pesquisa. Esta fórmula calcula o valor inteiro do piso do índice intermediário.
- O membro central da matriz é contrastado com o valor alvo. Retornamos o índice do elemento do meio se eles forem iguais. Alteramos o limite direito para um a menos que o índice do meio se o valor desejado for menor que o elemento do meio. Caso contrário, ajustamos a borda esquerda para que fique um a mais que o índice central. Continuamos fazendo isso até que o valor da meta seja obtido ou o espaço de busca seja preenchido.
- A complexidade temporal do algoritmo de busca binária, onde n é o tamanho do array, é O(log n). Isso é muito mais eficiente que a busca linear, que tem uma complexidade temporal de O(n), onde n é o tamanho do array.
- Finalmente, a técnica de busca binária oferece uma maneira útil de localizar um membro específico em um array ordenado. É fácil de construir e possui complexidade de tempo O(log n), tornando-o uma abordagem eficiente para grandes conjuntos de dados.
Vantagens:
- Para grandes conjuntos de dados, o algoritmo de pesquisa binária é excepcionalmente eficiente e é capaz de lidar com uma ampla variedade de tamanhos de entrada.
- O algoritmo é simples de implementar em quase todas as linguagens de programação.
Desvantagens:
- Antes de usar a técnica de busca binária, o array de entrada deve ser classificado, o que consome mais tempo e memória.
- O algoritmo não pode ser aplicado a matrizes não classificadas.
- O algoritmo pode produzir resultados imprecisos se a matriz de entrada não estiver classificada.
- O algoritmo de busca binária não é apropriado para conjuntos de dados minúsculos, pois a sobrecarga da técnica pode superar seus benefícios.
Conclusão:
Uma matriz classificada pode ser pesquisada rapidamente por um elemento específico usando a técnica de pesquisa binária. Ele emprega uma estratégia de dividir e conquistar para reduzir o intervalo de pesquisa pela metade a cada iteração, permitindo que seja altamente eficiente para grandes conjuntos de dados. No entanto, antes de usar a técnica de pesquisa binária, o array de entrada deve ser classificado, o que consome mais tempo e memória. O algoritmo de busca binária é uma ferramenta sofisticada de processamento de dados amplamente utilizada em diversos setores.