Learn Linear Search in 3 minutes ⬇️

Full Transcript

https://www.youtube.com/watch?v=246V51AWwZM

[00:04] All right everybody linear searches we need to talk about linear searches because this wouldn't be a complete course without them.
[00:12] With a linear search, we iterate through a collection one element at a time.
[00:18] The runtime complexity of a linear search is big O of N.
[00:22] The larger the data set, the number of steps to complete that search will increase proportionately.
[00:27] The disadvantages of a linear search is that they are slow for large data sets.
[00:32] But with the advantages, they are fast for searches of small to medium sized data sets and they don't need to be sorted.
[00:37] That's a huge benefit over binary searches and interpolation searches.
[00:44] And they are useful for data structures that do not have random access such as linked lists.
[00:47] So let's begin.
[00:49] Let's create a basic array of integers.
[00:52] Int array and to make up some numbers, they don't necessarily need to be in order.
[01:00] All right then let's find an index.
[01:00] Int index equals and we will invoke a linear
[01:05] index equals and we will invoke a linear search function which we still need to declare.
[01:07] We will pass in our array and some value we would like to search for.
[01:11] Uh, let's search for the number one, okay?
[01:14] So then, let's declare this function.
[01:16] Create method linear search private.
[01:19] Static and linear search, so we have two parameters, an integer array and an integer.
[01:24] I'm going to rename i as value, so it's more descriptive.
[01:29] Okay, with a linear search, all we need to do is loop through our array one element at a time.
[01:34] So we can do that with the for loop.
[01:39] So let's set into i our index equal to zero.
[01:43] We will continue this as long as i is less than our arrays length, then increment i by one.
[01:51] What we're checking with an if statement is to see if our array at index of i is equal to the value that we're searching for.
[02:00] This parameter, if it is, then let's return whatever our index is, i.
[02:07] index is i if we do not find it after iterating
[02:09] if we do not find it after iterating through our entire array let's return
[02:11] through our entire array let's return negative 1 as a sentinel value and
[02:14] negative 1 as a sentinel value and that's all there is to it to our linear
[02:16] that's all there is to it to our linear search function so back within our main
[02:18] search function so back within our main function let's check to see if the value
[02:21] function let's check to see if the value returned does not equal negative one
[02:24] returned does not equal negative one that means that we found our value so
[02:26] that means that we found our value so with an if else statement
[02:29] with an if else statement let's check to see if index does not
[02:32] let's check to see if index does not equal negative one that means that we
[02:35] equal negative one that means that we have found our element so let's print
[02:38] have found our element so let's print element found at
[02:40] element found at index
[02:41] index plus index
[02:44] plus index else let's print element not found
[02:47] else let's print element not found system.out.printline
[02:49] system.out.printline element not found
[02:51] element not found so if we're searching for the number one
[02:54] so if we're searching for the number one we would find that at index one
[02:57] we would find that at index one zero one if we search for five
[03:01] zero one if we search for five that is found at index eight zero one
[03:04] that is found at index eight zero one two three four five six seven eight if
[03:07] two three four five six seven eight if there's some number that's not in here
[03:08] there's some number that's not in here like 10
[03:09] like 10 then this will print element not found
[03:12] then this will print element not found so yeah that's the idea behind a linear
[03:14] so yeah that's the idea behind a linear search we iterate through some
[03:16] search we iterate through some collection one element at a time it's
[03:19] collection one element at a time it's slow for large data sets but it's fast
[03:21] slow for large data sets but it's fast for small to medium data sets this would
[03:23] for small to medium data sets this would be a small data set and they do not need
[03:26] to be sorted that's a huge advantage so
[03:29] to be sorted that's a huge advantage so yeah everybody that is a linear search
[03:31] yeah everybody that is a linear search if you would like a copy of this code
[03:33] if you would like a copy of this code i'll post this to the comment section
[03:34] i'll post this to the comment section down below and well yeah that is a basic
[03:37] down below and well yeah that is a basic linear search in computer science i
[03:40] linear search in computer science i guess

Full Transcript

https://www.youtube.com/watch?v=246V51AWwZM
Translation: pt-BR

[00:04] Tudo bem, pessoal, buscas lineares. Precisamos falar sobre buscas lineares porque este não seria um curso completo sem elas.
[00:12] Com uma busca linear, iteramos por uma coleção, um elemento de cada vez.
[00:18] A complexidade de tempo de execução de uma busca linear é Big O de N.
[00:22] Quanto maior o conjunto de dados, o número de passos para completar essa busca aumentará proporcionalmente.
[00:27] As desvantagens de uma busca linear é que elas são lentas para grandes conjuntos de dados.
[00:32] Mas com as vantagens, elas são rápidas para buscas em conjuntos de dados de pequeno a médio porte e não precisam ser ordenadas.
[00:37] Esse é um grande benefício em relação às buscas binárias e de interpolação.
[00:44] E elas são úteis para estruturas de dados que não possuem acesso aleatório, como listas ligadas.
[00:47] Então, vamos começar.
[00:49] Vamos criar um array básico de inteiros.
[00:52] Array de inteiros e para inventar alguns números, eles não precisam necessariamente estar em ordem.
[01:00] Tudo bem, então vamos encontrar um índice.
[01:00] Int index igual e vamos invocar uma linear
[01:05] o índice é igual e invocaremos uma função de busca linear que ainda precisamos declarar.
[01:07] Passaremos nosso array e algum valor que gostaríamos de procurar.
[01:11] Uh, vamos procurar o número um, ok?
[01:14] Então, vamos declarar esta função.
[01:16] Criar método busca linear privada.
[01:19] Estática e busca linear, então temos dois parâmetros, um array de inteiros e um inteiro.
[01:24] Vou renomear i para valor, para ser mais descritivo.
[01:29] Ok, com uma busca linear, tudo o que precisamos fazer é percorrer nosso array um elemento de cada vez.
[01:34] Então podemos fazer isso com o loop for.
[01:39] Então vamos definir em i nosso índice igual a zero.
[01:43] Continuaremos isso enquanto i for menor que o comprimento do nosso array, então incrementaremos i em um.
[01:51] O que estamos verificando com uma instrução if é para ver se nosso array no índice i é igual ao valor que estamos procurando.
[02:00] Este parâmetro, se for, então vamos retornar o que quer que seja nosso índice, i.
[02:07] o índice é i se não o encontrarmos após iterar
[02:09] se não o encontrarmos após iterar por todo o nosso array, vamos retornar
[02:11] por todo o nosso array, vamos retornar -1 como um valor sentinela e
[02:14] -1 como um valor sentinela e é só isso para nossa linear
[02:16] é só isso para nossa função de busca linear, então de volta à nossa principal
[02:18] função de busca, então de volta à nossa função principal, vamos verificar se o valor
[02:21] função, vamos verificar se o valor retornado não é igual a -1
[02:24] retornado não é igual a -1, isso significa que encontramos nosso valor, então
[02:26] isso significa que encontramos nosso valor, então com uma instrução if else
[02:29] com uma instrução if else, vamos verificar se o índice não
[02:32] vamos verificar se o índice não é igual a -1, isso significa que nós
[02:35] igual a -1, isso significa que encontramos nosso elemento, então vamos imprimir
[02:38] encontramos nosso elemento, então vamos imprimir elemento encontrado em
[02:40] elemento encontrado no índice
[02:41] índice mais índice
[02:44] mais índice, caso contrário, vamos imprimir elemento não encontrado
[02:47] caso contrário, vamos imprimir elemento não encontrado system.out.printline
[02:49] system.out.printline elemento não encontrado
[02:51] elemento não encontrado, então se estivermos procurando pelo número um
[02:54] então se estivermos procurando pelo número um, nós o encontraríamos no índice um
[02:57] nós o encontraríamos no índice um, zero, um, se procurarmos por cinco
[03:01] zero, um, se procurarmos por cinco, ele é encontrado no índice oito, zero, um
[03:04] ele é encontrado no índice oito, zero, um, dois, três, quatro, cinco, seis, sete, oito, se
[03:07] dois três quatro cinco seis sete oito se houver algum número que não esteja aqui
[03:08] há algum número que não está aqui como 10
[03:09] como 10 então isso imprimirá elemento não encontrado
[03:12] então isso imprimirá elemento não encontrado então sim essa é a ideia por trás de um linear
[03:14] então sim essa é a ideia por trás de uma busca linear nós iteramos por alguma
[03:16] busca nós iteramos por alguma coleção um elemento de cada vez é
[03:19] coleção um elemento de cada vez é lento para grandes conjuntos de dados mas é rápido
[03:21] lento para grandes conjuntos de dados mas é rápido para conjuntos de dados pequenos a médios isso seria
[03:23] para conjuntos de dados pequenos a médios este seria um pequeno conjunto de dados e eles não precisam
[03:26] ser ordenados essa é uma grande vantagem então
[03:29] ser ordenados essa é uma grande vantagem então sim todo mundo que é uma busca linear
[03:31] sim todo mundo que é uma busca linear se você gostaria de uma cópia deste código
[03:33] se você gostaria de uma cópia deste código eu postarei isso na seção de comentários
[03:34] eu postarei isso na seção de comentários abaixo e bem sim esse é um básico
[03:37] abaixo e bem sim esse é um básico busca linear em ciência da computação eu
[03:40] busca linear em ciência da computação eu acho

Full Transcript (Bilingual)

https://www.youtube.com/watch?v=246V51AWwZM
Translation: pt-BR

[00:04] All right everybody linear searches we need to talk about linear searches because this wouldn't be a complete course without them.
Tudo bem, pessoal, buscas lineares. Precisamos falar sobre buscas lineares porque este não seria um curso completo sem elas.

[00:12] With a linear search, we iterate through a collection one element at a time.
Com uma busca linear, iteramos por uma coleção, um elemento de cada vez.

[00:18] The runtime complexity of a linear search is big O of N.
A complexidade de tempo de execução de uma busca linear é Big O de N.

[00:22] The larger the data set, the number of steps to complete that search will increase proportionately.
Quanto maior o conjunto de dados, o número de passos para completar essa busca aumentará proporcionalmente.

[00:27] The disadvantages of a linear search is that they are slow for large data sets.
As desvantagens de uma busca linear é que elas são lentas para grandes conjuntos de dados.

[00:32] But with the advantages, they are fast for searches of small to medium sized data sets and they don't need to be sorted.
Mas com as vantagens, elas são rápidas para buscas em conjuntos de dados de pequeno a médio porte e não precisam ser ordenadas.

[00:37] That's a huge benefit over binary searches and interpolation searches.
Esse é um grande benefício em relação às buscas binárias e de interpolação.

[00:44] And they are useful for data structures that do not have random access such as linked lists.
E elas são úteis para estruturas de dados que não possuem acesso aleatório, como listas ligadas.

[00:47] So let's begin.
Então, vamos começar.

[00:49] Let's create a basic array of integers.
Vamos criar um array básico de inteiros.

[00:52] Int array and to make up some numbers, they don't necessarily need to be in order.
Array de inteiros e para inventar alguns números, eles não precisam necessariamente estar em ordem.

[01:00] All right then let's find an index.
Tudo bem, então vamos encontrar um índice.

[01:00] Int index equals and we will invoke a linear
Int index igual e vamos invocar uma linear

[01:05] index equals and we will invoke a linear search function which we still need to declare.
o índice é igual e invocaremos uma função de busca linear que ainda precisamos declarar.

[01:07] We will pass in our array and some value we would like to search for.
Passaremos nosso array e algum valor que gostaríamos de procurar.

[01:11] Uh, let's search for the number one, okay?
Uh, vamos procurar o número um, ok?

[01:14] So then, let's declare this function.
Então, vamos declarar esta função.

[01:16] Create method linear search private.
Criar método busca linear privada.

[01:19] Static and linear search, so we have two parameters, an integer array and an integer.
Estática e busca linear, então temos dois parâmetros, um array de inteiros e um inteiro.

[01:24] I'm going to rename i as value, so it's more descriptive.
Vou renomear i para valor, para ser mais descritivo.

[01:29] Okay, with a linear search, all we need to do is loop through our array one element at a time.
Ok, com uma busca linear, tudo o que precisamos fazer é percorrer nosso array um elemento de cada vez.

[01:34] So we can do that with the for loop.
Então podemos fazer isso com o loop for.

[01:39] So let's set into i our index equal to zero.
Então vamos definir em i nosso índice igual a zero.

[01:43] We will continue this as long as i is less than our arrays length, then increment i by one.
Continuaremos isso enquanto i for menor que o comprimento do nosso array, então incrementaremos i em um.

[01:51] What we're checking with an if statement is to see if our array at index of i is equal to the value that we're searching for.
O que estamos verificando com uma instrução if é para ver se nosso array no índice i é igual ao valor que estamos procurando.

[02:00] This parameter, if it is, then let's return whatever our index is, i.
Este parâmetro, se for, então vamos retornar o que quer que seja nosso índice, i.

[02:07] index is i if we do not find it after iterating
o índice é i se não o encontrarmos após iterar

[02:09] if we do not find it after iterating through our entire array let's return
se não o encontrarmos após iterar por todo o nosso array, vamos retornar

[02:11] through our entire array let's return negative 1 as a sentinel value and
por todo o nosso array, vamos retornar -1 como um valor sentinela e

[02:14] negative 1 as a sentinel value and that's all there is to it to our linear
-1 como um valor sentinela e é só isso para nossa linear

[02:16] that's all there is to it to our linear search function so back within our main
é só isso para nossa função de busca linear, então de volta à nossa principal

[02:18] search function so back within our main function let's check to see if the value
função de busca, então de volta à nossa função principal, vamos verificar se o valor

[02:21] function let's check to see if the value returned does not equal negative one
função, vamos verificar se o valor retornado não é igual a -1

[02:24] returned does not equal negative one that means that we found our value so
retornado não é igual a -1, isso significa que encontramos nosso valor, então

[02:26] that means that we found our value so with an if else statement
isso significa que encontramos nosso valor, então com uma instrução if else

[02:29] with an if else statement let's check to see if index does not
com uma instrução if else, vamos verificar se o índice não

[02:32] let's check to see if index does not equal negative one that means that we
vamos verificar se o índice não é igual a -1, isso significa que nós

[02:35] equal negative one that means that we have found our element so let's print
igual a -1, isso significa que encontramos nosso elemento, então vamos imprimir

[02:38] have found our element so let's print element found at
encontramos nosso elemento, então vamos imprimir elemento encontrado em

[02:40] element found at index
elemento encontrado no índice

[02:41] index plus index
índice mais índice

[02:44] plus index else let's print element not found
mais índice, caso contrário, vamos imprimir elemento não encontrado

[02:47] else let's print element not found system.out.printline
caso contrário, vamos imprimir elemento não encontrado system.out.printline

[02:49] system.out.printline element not found
system.out.printline elemento não encontrado

[02:51] element not found so if we're searching for the number one
elemento não encontrado, então se estivermos procurando pelo número um

[02:54] so if we're searching for the number one we would find that at index one
então se estivermos procurando pelo número um, nós o encontraríamos no índice um

[02:57] we would find that at index one zero one if we search for five
nós o encontraríamos no índice um, zero, um, se procurarmos por cinco

[03:01] zero one if we search for five that is found at index eight zero one
zero, um, se procurarmos por cinco, ele é encontrado no índice oito, zero, um

[03:04] that is found at index eight zero one two three four five six seven eight if
ele é encontrado no índice oito, zero, um, dois, três, quatro, cinco, seis, sete, oito, se

[03:07] two three four five six seven eight if there's some number that's not in here
dois três quatro cinco seis sete oito se houver algum número que não esteja aqui

[03:08] there's some number that's not in here like 10
há algum número que não está aqui como 10

[03:09] like 10 then this will print element not found
como 10 então isso imprimirá elemento não encontrado

[03:12] then this will print element not found so yeah that's the idea behind a linear
então isso imprimirá elemento não encontrado então sim essa é a ideia por trás de um linear

[03:14] so yeah that's the idea behind a linear search we iterate through some
então sim essa é a ideia por trás de uma busca linear nós iteramos por alguma

[03:16] search we iterate through some collection one element at a time it's
busca nós iteramos por alguma coleção um elemento de cada vez é

[03:19] collection one element at a time it's slow for large data sets but it's fast
coleção um elemento de cada vez é lento para grandes conjuntos de dados mas é rápido

[03:21] slow for large data sets but it's fast for small to medium data sets this would
lento para grandes conjuntos de dados mas é rápido para conjuntos de dados pequenos a médios isso seria

[03:23] for small to medium data sets this would be a small data set and they do not need
para conjuntos de dados pequenos a médios este seria um pequeno conjunto de dados e eles não precisam

[03:26] to be sorted that's a huge advantage so
ser ordenados essa é uma grande vantagem então

[03:29] to be sorted that's a huge advantage so yeah everybody that is a linear search
ser ordenados essa é uma grande vantagem então sim todo mundo que é uma busca linear

[03:31] yeah everybody that is a linear search if you would like a copy of this code
sim todo mundo que é uma busca linear se você gostaria de uma cópia deste código

[03:33] if you would like a copy of this code i'll post this to the comment section
se você gostaria de uma cópia deste código eu postarei isso na seção de comentários

[03:34] i'll post this to the comment section down below and well yeah that is a basic
eu postarei isso na seção de comentários abaixo e bem sim esse é um básico

[03:37] down below and well yeah that is a basic linear search in computer science i
abaixo e bem sim esse é um básico busca linear em ciência da computação eu

[03:40] linear search in computer science i guess
busca linear em ciência da computação eu acho

https://www.youtube.com/watch?v=246V51AWwZM

Summary

TL;DR — A linear search iterates through a collection one element at a time to find a specific value. While simple and effective for small datasets or unsorted data, its runtime complexity is O(N), making it inefficient for large datasets.

Key points

• Linear search examines each element sequentially until a match is found or the end of the collection is reached.

• Its time complexity is Big O of N, meaning the time taken grows linearly with the size of the dataset.

• Advantages include simplicity, speed on small to medium datasets, and the ability to work with unsorted data.

• A significant disadvantage is its slowness on large datasets.

• It is particularly useful for data structures like linked lists that do not support random access.

• The search returns the index of the found element or a sentinel value (like -1) if not found.

Takeaway — Linear search is a fundamental but often inefficient search algorithm best suited for small, unsorted collections or specific data structures.

Resumo / Summary (pt-BR)

Em resumo — A busca linear percorre uma coleção, um elemento de cada vez, para encontrar um valor específico. Embora seja simples e eficaz para conjuntos de dados pequenos ou não ordenados, sua complexidade de tempo é O(N), tornando-a ineficiente para grandes conjuntos de dados.

Pontos-chave

• A busca linear examina cada elemento sequencialmente até que uma correspondência seja encontrada ou o final da coleção seja alcançado.

• Sua complexidade de tempo é Big O de N, o que significa que o tempo necessário cresce linearmente com o tamanho do conjunto de dados.

• As vantagens incluem simplicidade, rapidez em conjuntos de dados pequenos a médios e a capacidade de funcionar com dados não ordenados.

• Uma desvantagem significativa é sua lentidão em grandes conjuntos de dados.

• É particularmente útil para estruturas de dados como listas ligadas que não suportam acesso aleatório.

• A busca retorna o índice do elemento encontrado ou um valor sentinela (como -1) se não for encontrado.

Conclusão — A busca linear é um algoritmo de busca fundamental, mas muitas vezes ineficiente, mais adequado para coleções pequenas e não ordenadas ou estruturas de dados específicas.