Busca Linear

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).