Busca Linear

Por
|

A busca linear é o algoritmo de busca mais simples para vetores e qualquer outro tipo de estrutura de dados linear (como a lista ligada/encadeada). Nesta postagem, focaremos nos vetores (ou arrays).

A ideia básica do algoritmo é comparar o elemento procurado com cada elemento do vetor até encontrá-lo partindo, em geral, da primeira posição do vetor.

Enquanto a busca binária só funciona em vetores ordenados, a busca linear funciona em qualquer vetor. Entretanto, a busca linear é menos eficiente que a busca binária.

Seu melhor caso ocorre quando o elemento procurado está na primeira posição do vetor e a complexidade, neste caso, é de O(1).

O pior caso ocorre quando o elemento não está no vetor e, neste caso, a complexidade no tempo é de O(n). O caso médio também é O(n).

Portanto, a busca linear é menos eficiente que a busca binária, que possui complexidade O(log n).

Códigos

Os códigos a seguir implementam a busca linear em Java e em C.

Código em Java

            /*
             * Código por Henrique Felipe (GitHub: HenriqueIni) 
             */
            public class LinearSearch {
                //procura o objeto 'key' no vetor 'a'
                public static int linearSearch(Object[] a, Object key){
                    for(int i = 0; i < a.length; i++){
                        if(a[i].equals(key)){
                            return i; //valor encontrado, retorna o índice
                        }
                    }
                    return -1; //valor não encontrado
                }
                //procura o valor 'key' no vetor 'a'
                public static int linearSearch(int[] a, int key){
                    for(int i = 0; i < a.length; i++){
                        if(a[i] == key){
                            return i; //valor encontrado, retorna o índice
                        }
                    }
                    return -1; //valor não encontrado
                }
                //Código de testes
                public static void main(String[] args) {
                    int[] a1 = {2, 3, 8, -1, -4, 20, 0, 5};
                    String[] a2 = {"Hello", "World"};
                    System.out.println("Key = 20, Index = " + linearSearch(a1, 20));
                    System.out.println("Key = \"World\", Index = " + linearSearch(a2, "World"));
                    System.out.println("Key = 9, Index = " + linearSearch(a1, 9));
                    System.out.println("Key = \"Java\", Index = " + linearSearch(a2, "Java"));
                }
            }
            

Código em C

            /*
             * Código por Henrique Felipe (GitHub: HenriqueIni) 
             */
            #include <stdio.h>
            #include <stdlib.h>

            //busca o valor 'key' no vetor 'a'
            int linearSearch(int a[], int size, int key) {
                int i;
                for (i = 0; i < size; i++) {
                    if (a[i] == key) {
                        return i;//valor encontrado, retorna o índice
                    }
                }
                return -1;//valor não encontrado
            }

            //Código de testes
            int main() {
                int a[] = {2, 3, 8, -1, -4, 20, 0, 5};
                int size = 8;
                printf("Key = 20, Index = %d\n", linearSearch(a, size, 20));
                printf("Key = 9, Index = %d", linearSearch(a, size, 9));
                return 0;
            }
            

Download dos Códigos

Os códigos também estão disponíveis no Google Drive: Busca Linear (Java/C).

Siga o blog por e-mail

Receba notificações de novas postagens e novidades do blog por e-mail.

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário