Neste artigo, discutiremos o algoritmo de pesquisa binária. Pesquisar é o processo de encontrar algum elemento específico na lista. Se o elemento estiver presente na lista, o processo será considerado bem-sucedido e retornará a localização desse elemento. Caso contrário, a pesquisa será considerada malsucedida.
Pesquisa Linear e Pesquisa Binária são as duas técnicas de pesquisa populares. Aqui discutiremos o algoritmo de pesquisa binária.
A pesquisa binária é a técnica de pesquisa que funciona de forma eficiente em listas ordenadas. Portanto, para pesquisar um elemento em alguma lista usando a técnica de pesquisa binária, devemos garantir que a lista esteja ordenada.
A pesquisa binária segue a abordagem de dividir e conquistar, na qual a lista é dividida em duas metades e o item é comparado com o elemento intermediário da lista. Se a correspondência for encontrada, a localização do elemento do meio será retornada. Caso contrário, pesquisamos qualquer uma das metades dependendo do resultado produzido na partida.
NOTA: A pesquisa binária pode ser implementada em elementos ordenados do array. Se os elementos da lista não estiverem organizados de maneira ordenada, primeiro precisamos classificá-los.
Agora, vamos ver o algoritmo da Pesquisa Binária.
Algoritmo
Binary_Search(a, lower_bound, upper_bound, val) // 'a' is the given array, 'lower_bound' is the index of the first array element, 'upper_bound' is the index of the last array element, 'val' is the value to search Step 1: set beg = lower_bound, end = upper_bound, pos = - 1 Step 2: repeat steps 3 and 4 while beg val set end = mid - 1 else set beg = mid + 1 [end of if] [end of loop] Step 5: if pos = -1 print 'value is not present in the array' [end of if] Step 6: exit
Funcionamento da pesquisa binária
Agora, vamos ver o funcionamento do Algoritmo de Pesquisa Binária.
Para entender o funcionamento do algoritmo de pesquisa binária, vamos pegar um array classificado. Será fácil entender o funcionamento da pesquisa binária com um exemplo.
Existem dois métodos para implementar o algoritmo de pesquisa binária -
- Método iterativo
- Método recursivo
O método recursivo de pesquisa binária segue a abordagem de dividir para conquistar.
Deixe os elementos do array serem -
Deixe o elemento a ser pesquisado ser, K = 56
Temos que usar a fórmula abaixo para calcular o meio da matriz -
mid = (beg + end)/2
Então, na matriz fornecida -
implorar = 0
fim = 8
meio = (0 + 8)/2 = 4. Portanto, 4 é o meio do array.
Agora, o elemento a ser pesquisado foi encontrado. Portanto, o algoritmo retornará o índice do elemento correspondente.
Complexidade da pesquisa binária
Agora, vamos ver a complexidade de tempo da pesquisa binária no melhor caso, no caso médio e no pior caso. Veremos também a complexidade espacial da pesquisa binária.
1. Complexidade de tempo
| Caso | Complexidade de tempo |
|---|---|
| Melhor caso | O(1) |
| Caso médio | O(logn) |
| Pior caso | O(logn) |
2. Complexidade Espacial
| Complexidade Espacial | O(1) |
- A complexidade espacial da pesquisa binária é O(1).
Implementação de Pesquisa Binária
Agora vamos ver os programas de busca binária em diferentes linguagens de programação.
Programa: Escreva um programa para implementar pesquisa binária em linguagem C.
#include int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; /* if the item to be searched is present at middle */ if(a[mid] == val) { return mid+1; } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; int main() a[]="{11," 14, 25, 30, 40, 41, 52, 57, 70}; given array val="40;" value n="sizeof(a)" sizeof(a[0]); size of res="binarySearch(a," 0, n-1, store result printf('the elements are - '); for (int i="0;" < n; i++) printf('%d ', a[i]); printf('
element %d', (res="=" -1) not present array'); at %d position array', res); 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-5.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in C++.</p> <pre> #include using namespace std; int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; /* if the item to be searched is present at middle */ if(a[mid] == val) { return mid+1; } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; int main() a[]="{10," 12, 24, 29, 39, 40, 51, 56, 70}; given array val="51;" value n="sizeof(a)" sizeof(a[0]); size of res="binarySearch(a," 0, n-1, store result cout<<'the elements are - '; for (int i="0;" < n; i++) cout< <a[i]<<' cout<<'
element '<<val; (res="=" -1) not present array'; at '<<res<<' position 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-6.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in C#.</p> <pre> using System; class BinarySearch { static int binarySearch(int[] a, int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; if(a[mid] == val) { return mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; static void main() int[] a="{9," 11, 23, 28, 38, 45, 50, 56, 70}; given array int val="70;" value n="a.Length;" size of res="binarySearch(a," 0, n-1, store result console.write('the elements are - '); for (int i="0;" < n; i++) console.write(a[i] + ' console.writeline(); console.writeline('element (res="=" -1) not present array'); at position pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-7.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in Java.</p> <pre> class BinarySearch { static int binarySearch(int a[], int beg, int end, int val) { int mid; if(end >= beg) { mid = (beg + end)/2; if(a[mid] == val) { return mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if(a[mid] <val) { return binarysearch(a, mid+1, end, val); } * if the item to be searched is greater than middle, then it can only in right subarray else beg, mid-1, -1; public static void main(string args[]) int a[]="{8," 10, 22, 27, 37, 44, 49, 55, 69}; given array val="37;" value n="a.length;" size of res="binarySearch(a," 0, n-1, store result system.out.print('the elements are: '); for (int i="0;" < n; i++) system.out.print(a[i] + ' system.out.println(); system.out.println('element is: (res="=" -1) not present array'); at position pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-8.webp" alt="Binary Search Algorithm"> <p> <strong>Program:</strong> Write a program to implement Binary search in PHP.</p> <pre> = $beg) { $mid = floor(($beg + $end)/2); if($a[$mid] == $val) { return $mid+1; /* if the item to be searched is present at middle */ } /* if the item to be searched is smaller than middle, then it can only be in left subarray */ else if($a[$mid] <$val) { return binarysearch($a, $mid+1, $end, $val); } * if the item to be searched is greater than middle, then it can only in right subarray else $beg, $mid-1, -1; $a="array(7," 9, 21, 26, 36, 43, 48, 54, 68); given array $val="68;" value $n="sizeof($a);" size of $res="binarySearch($a," 0, $n-1, store result echo 'the elements are: '; for ($i="0;" $i < $n; $i++) ' , $a[$i]; <br>' , 'Element to be searched is: ' , $val; if ($res == -1) echo ' <br>' , 'Element is not present in the array'; else echo ' <br>' , 'Element is present at ' , $res , ' position of array'; ?> </$val)></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/10/binary-search-algorithm-9.webp" alt="Binary Search Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></val)></pre></val)></pre></val)></pre></val)> Saída
Então, isso é tudo sobre o artigo. Espero que o artigo seja útil e informativo para você.