Eu vivo usando binary search na vida real. Uma vez eu não tava conseguindo descobrir onde tava o erro em um código, aí eu fui rodando ele parcialmente seguindo a lógica de binary search. Assim deu pra rapidamente descobrir qual das 3000 linhas do arquivo estava causando aquilo.
@@saca_isso Acho que foi em JS, alguma coisa tava quebrando a página toda, mas não dava uma mensagem de erro que indicava claramente o que tava acontecendo. Então eu fui deletando metade do código e rodando de novo. Se o erro parasse de acontecer, eu sabia que o problema tava na metade que eu deletei. Se ainda ocorresse, estaria na metade que eu mantive. Aí fui repetindo isso até achar o trecho de código problemático.
@@kuroikenshi600o git tem uma ferramenta chamada bisect que faz justamente isso aplica busca binaria nos commits pra encontrar qual deles introduziu um bug. Vale a pena conferir
@@kuroikenshi600 Mas como você garantia, por exemplo, que ao remover a segunda metade do código não estava, também, removendo alguma função que estava sendo chamada na primeira metade?
Acho q sou mt lerdo pra essa profissao, penso em tentar seguir a carreira como programador, mas tava lendo o livro q ele recomenda "entendendo algoritimos" e qnd li a parte de binary search eu fiquei meio confuso, sei q e algo muito simples mas n entrou de primeira na minha cabeca, finalmente teve um video explicando como funciona pq eu n tinha ideia de como q implimentava esse algoritimo.
cara blz mas pra q q eu ia precisar disso? tipo e se os targets n for numeros? no caso isso ai só é bom pra quando os elementos da array for numeros é? perdoe-me pela falta de informação, mas, eu decidi perguntar antes de pesquisar ou ir atras, vou começar a ver estrutura de dados e algoritmos amanhã
Muito bom cara. Posso deixar um pedido? Gostaria de ver você explicar de maneira didática o Leetcode 18, chamado 4Sum. Fiquei sabendo, através de um amigo, que caiu na entrevista do Mercado Livre. Achei bem chato e tive que consultar. Ele exige mexer com mais de 2 ponteiros, acho que seria legal uma explicação. Pelo que pesquisei, ninguém explicou esse visualmente em pt-br no youtube ainda.
Eu tava estudando isso ontem e fiquei com algumas dúvidas. 1 - Se eu tenho um array grande, desordenado e preciso buscar mais de um elemento, valhe mais eu combinar binarySearch + sort? 2 - BinarySearch é válido pra quando eu preciso, além da busca, realizar uma inserção ou remoção de um elemento?
Depende muito, mas se vc tem varias buscas talvez fosse melhor criar um Hash do seu array (O(n)) e entao buscar pelo indice O(1) .. mas como falei depende de outras coisas... existem tb quicksort ...
Cara respondendo sua 2 pergunta, o proprio nome ja diz. BinarySearch é somente busca, nada de inserir ou remover. Se voce quiser adicionar ou remover tera que criar funções auxiliadoras e usar o binarySearch apenas para achar o index que quer remover por exemplo.
Existe uma estrutura que permite a inserção e remoção em log(n) e a busca em log(n), em C++ é o ordered_set. Suponho que existam estruturas similares em outras linguagens. Nesse caso por ser um set ele não permite elementos repetidos.
Se é necessário inserir e remover elementos, acho que você pode usar uma árvore binária de busca, que é uma árvore que segue a mesma lógica do binary search. Sobre combinar sort + binary search, o sort seria O(N logN) o que é maior do que O(N) que seria uma busca linear normal. Então só vale a pena se for realizar muitas buscas num array. Você poderia fazer o sort como uma preparação, tipo um loading inicial, pra depois poder aplicar o binarysearch durante a interação do usuário.
galego, eu sou pessimo pessimo, em leetcode e esses outros sites de desafios e recentemente eu fiz um processo seletivo pra uma empresa e caiu muitos desafios estilo leetcode, e eu percebi que esse e meu maior ponto fraco como dev, voce acha que o seu curso me ajudaria ou ainda não é o momento para ele?
pra melhorar o runtime não seria interessante checar se o m não é o target primeiro? iria tornar o resto do trecho unreachable e só executaria o necessário
@@joaopedrofernandes2497 é mais provavel que não seja o target do que seja o terget. Como muito provavelmente não é o target, é mais provavel que seja maior ou menor, então é um pouquinho mais eficiente fazer esses checks antes. Mas assim, no mundo real, isso é completamente irrelevante em absolutamente todos os cenarios
-1 é quando o target (que é o numero que ele quer encontrar no array) não se encontra dentro do array. caso contrario ele retorna o index onde target está. Por exemplo [-1, 0, 3, 5, 12] e eu coloco o target 9, o retorno será -1 porque 9 não existe neste array. Mas caso fosse [-1, 0, 3, 5, 9, 12] o retorno já seria 4, porque o 9 se encontra no index 4. Espero que tenha ajudado!
No enunciado do problema é dito que, caso o target não esteja no array, o programa retorne -1, indicando que o target não existe e portanto não pode ser encontrado. No primeiro parágrafo diz: " if target exists, then return its index. Otherwise, return -1" ou caso você não saiba inglês, "se o alvo existe, retorne seu índice. Caso contrário, retorne -1."
é uma exigência do enunciado do problema no próprio leetcode. mas caso vc implemente por conta própria no seu próprio editor pra treinar, pode retornar uma mensagem avisando que o target não existe no array ao invés do -1.
Complementando o que a galera disse, o retorno de -1 é quase como uma "boa prática" ou convenção quando é um algoritmo de busca de índices. Como os índices são de 0 a n, retornar -1 é como dizer que não foi encontrado sem mudar o tipo do retorno, ao invés de jogar uma excessão(erro) ou retornar um outro tipo que não seja um inteiro
Uma dúvida besta na prática o que um ponteiro a mais consome? Tipo a vantagem de 1 para 2 e de 2 para 4 e assim por diante. Imagino eu que o mais impactado seria memória.
Reduz ridiculamente o tempo de busca. Em vez de percorrer cada item você corta pela metade o número de buscas. Numa lista de 10 itens parece bobeira, mas imagina uma lista com 10 mil itens?
@@bituca__ Fiz um teste com uma lista de 1kk de int, 1000 iterações e medi os tempos, seguem os resultados: Tempo médio com 1 ponteiros: 0.000002 segundos Tempo médio com 2 ponteiros: 0.000008 segundos Tempo médio com 4 ponteiros: 0.000004 segundos Tempo médio com 8 ponteiros: 0.000006 segundos Tempo médio com 10 ponteiros: 0.000009 segundos Ponteiros Tempo (s) 0 1 0.000002 1 2 0.000008 2 4 0.000004 3 8 0.000006 4 10 0.000009 Todas as vezes 1 ponteiro só foi mais rápido, talvez pelo tipo de implementação, mas os resultados foram Proximo's a esse na grande maioria dos casos.
import time import random import pandas as pd import matplotlib.pyplot as plt # Função para busca binária com 1 ponteiro (divisão clássica) def binary_search_1_pointer(arr, target): left, right = 0, len(arr) - 1 while left 0: left = points[i - 1] + 1 break else: left = points[-1] + 1 return -1 # Função para medir o tempo de busca com múltiplas repetições def measure_performance(search_func, arr, target, k=1, repetitions=1000): total_time = 0 for _ in range(repetitions): start_time = time.time() if k == 1: search_func(arr, target) else: search_func(arr, target, k) total_time += time.time() - start_time return total_time / repetitions # Lista de 1.000.000 itens ordenados arr = list(range(10000000)) # Elemento que vamos buscar target = random.choice(arr) # Número de ponteiros a serem testados (1, 2, 4, 8, 10) pointer_counts = [1, 2, 4, 8, 10] # Dicionário para armazenar os resultados de tempo performance_results = {} # Medir desempenho para diferentes ponteiros for k in pointer_counts: if k == 1: time_taken = measure_performance(binary_search_1_pointer, arr, target) else: time_taken = measure_performance(binary_search_multi_pointer, arr, target, k)
performance_results[k] = time_taken print(f"Tempo médio com {k} ponteiros: {time_taken:.6f} segundos") # Criar um DataFrame para os resultados df = pd.DataFrame(list(performance_results.items()), columns=["Ponteiros", "Tempo (s)"]) # Exibir o DataFrame print(df) # Plotar os resultados plt.figure(figsize=(10, 6)) plt.plot(df["Ponteiros"], df["Tempo (s)"], marker='o', linestyle='-', color='b') plt.title("Desempenho da Busca Binária com Diferentes Quantidades de Ponteiros (Média de 1000 Repetições)") plt.xlabel("Número de Ponteiros") plt.ylabel("Tempo (s)") plt.grid(True) plt.show()
@@leo1722467 Numa máquina moderna o código compila rápido mesmo. O tempo de compilação de uma binary search com 2 pointers é de O (log n), o segundo mais rápido. Com 1 pointer é O(n), o terceiro mais rápido. Olhando no gráfico, vê-se que a O(n) supera o O(log n) apenas quando a quantidade de elementos for pequena. Eu sugeriria aumentar pra 1 bilhão de itens, ou 1 tri, e comparar. Se aumentar o número de pointers o código vai ficando lento mesmo.
Assisti em 2x e agora tenho que assistir dnv
Usa binary search no video pra achar as lacunas do conhecimento... garanto que o video ja ta ordenado
Assisti em .5x e agora tenho q assistir novamente pela quarta vez.
Tenho TDAH
Quem é o Galego? "O nosso Indiano BR"
realmente o galego e uma alma iluminada, eu ia ir mendigar o curso no email, mas sinceramente vc merece o valor que eu vou pagar.
a primeira estratégia q vem a cabeça é usando recursão, mas essa solução de ir controlando via índices é bem melhor. Parabéns pelo conteúdo!
Sinceramente, um dos melhores achados foi esse canal.. sem comparação
muito bom. Tive prova de complexidade de algoritmos na semana retrasada e tinha uma questão justamente para implementar uma binary search. Otimo video
Eu estava lendo o Entendendo algoritmos hoje mais cedo e vi esse algoritmo lá, a sua explicação me ajudou muito
Augusto Galego, meu amigo parabéns pelo seu canal, principalmente essa série de 5 minutos, muito bom!!!!!!!!!!!!!
Eu vivo usando binary search na vida real. Uma vez eu não tava conseguindo descobrir onde tava o erro em um código, aí eu fui rodando ele parcialmente seguindo a lógica de binary search. Assim deu pra rapidamente descobrir qual das 3000 linhas do arquivo estava causando aquilo.
Como?
@@saca_isso Acho que foi em JS, alguma coisa tava quebrando a página toda, mas não dava uma mensagem de erro que indicava claramente o que tava acontecendo.
Então eu fui deletando metade do código e rodando de novo. Se o erro parasse de acontecer, eu sabia que o problema tava na metade que eu deletei. Se ainda ocorresse, estaria na metade que eu mantive. Aí fui repetindo isso até achar o trecho de código problemático.
@@kuroikenshi600o git tem uma ferramenta chamada bisect que faz justamente isso aplica busca binaria nos commits pra encontrar qual deles introduziu um bug. Vale a pena conferir
@@kuroikenshi600 o cara é um genio, valeu por compartilhar isso
@@kuroikenshi600 Mas como você garantia, por exemplo, que ao remover a segunda metade do código não estava, também, removendo alguma função que estava sendo chamada na primeira metade?
Muito top!
Valeu demais Galego, tu é foda
Adoraria ver uns videos teus de algoritmos pra fluxo em grafos
Poderia ensinar os outros tipos de arvore nessa pegada também. Ótimo vídeo.
Acho q sou mt lerdo pra essa profissao, penso em tentar seguir a carreira como programador, mas tava lendo o livro q ele recomenda "entendendo algoritimos" e qnd li a parte de binary search eu fiquei meio confuso, sei q e algo muito simples mas n entrou de primeira na minha cabeca, finalmente teve um video explicando como funciona pq eu n tinha ideia de como q implimentava esse algoritimo.
Ótimo conteúdo 👏👏
cara blz mas pra q q eu ia precisar disso?
tipo e se os targets n for numeros? no caso isso ai só é bom pra quando os elementos da array for numeros é?
perdoe-me pela falta de informação, mas, eu decidi perguntar antes de pesquisar ou ir atras, vou começar a ver estrutura de dados e algoritmos amanhã
Muito bom cara. Posso deixar um pedido? Gostaria de ver você explicar de maneira didática o Leetcode 18, chamado 4Sum. Fiquei sabendo, através de um amigo, que caiu na entrevista do Mercado Livre. Achei bem chato e tive que consultar. Ele exige mexer com mais de 2 ponteiros, acho que seria legal uma explicação. Pelo que pesquisei, ninguém explicou esse visualmente em pt-br no youtube ainda.
Qual a complexidade para ordenar um array de dados brutos?
Eu tava estudando isso ontem e fiquei com algumas dúvidas.
1 - Se eu tenho um array grande, desordenado e preciso buscar mais de um elemento, valhe mais eu combinar binarySearch + sort?
2 - BinarySearch é válido pra quando eu preciso, além da busca, realizar uma inserção ou remoção de um elemento?
Depende muito, mas se vc tem varias buscas talvez fosse melhor criar um Hash do seu array (O(n)) e entao buscar pelo indice O(1) .. mas como falei depende de outras coisas... existem tb quicksort ...
Cara respondendo sua 2 pergunta, o proprio nome ja diz. BinarySearch é somente busca, nada de inserir ou remover. Se voce quiser adicionar ou remover tera que criar funções auxiliadoras e usar o binarySearch apenas para achar o index que quer remover por exemplo.
Existe uma estrutura que permite a inserção e remoção em log(n) e a busca em log(n), em C++ é o ordered_set. Suponho que existam estruturas similares em outras linguagens. Nesse caso por ser um set ele não permite elementos repetidos.
Não é uma implementação trivial kkkkkkk
Se é necessário inserir e remover elementos, acho que você pode usar uma árvore binária de busca, que é uma árvore que segue a mesma lógica do binary search.
Sobre combinar sort + binary search, o sort seria O(N logN) o que é maior do que O(N) que seria uma busca linear normal. Então só vale a pena se for realizar muitas buscas num array. Você poderia fazer o sort como uma preparação, tipo um loading inicial, pra depois poder aplicar o binarysearch durante a interação do usuário.
VAI GALEGAO
O que tem de binary nesse search?
Vou colocar no 0,25 e tu vai ganhar 20m da minha vida
galego, eu sou pessimo pessimo, em leetcode e esses outros sites de desafios e recentemente eu fiz um processo seletivo pra uma empresa e caiu muitos desafios estilo leetcode, e eu percebi que esse e meu maior ponto fraco como dev, voce acha que o seu curso me ajudaria ou ainda não é o momento para ele?
@@dulii4238 ajuda bastante sim, com certeza. Foi feito com isso em mente
pra melhorar o runtime não seria interessante checar se o m não é o target primeiro? iria tornar o resto do trecho unreachable e só executaria o necessário
@@joaopedrofernandes2497 é mais provavel que não seja o target do que seja o terget. Como muito provavelmente não é o target, é mais provavel que seja maior ou menor, então é um pouquinho mais eficiente fazer esses checks antes.
Mas assim, no mundo real, isso é completamente irrelevante em absolutamente todos os cenarios
Muito bom!!
mas isso só funciona se for uma lista numerica ?
vim pelo mano devin
blond galego
pode explicar o porquê do return -1? não entendi muito bem
ele retorna -1 quando o número n existe no array
-1 é quando o target (que é o numero que ele quer encontrar no array) não se encontra dentro do array. caso contrario ele retorna o index onde target está.
Por exemplo [-1, 0, 3, 5, 12] e eu coloco o target 9, o retorno será -1 porque 9 não existe neste array.
Mas caso fosse [-1, 0, 3, 5, 9, 12] o retorno já seria 4, porque o 9 se encontra no index 4.
Espero que tenha ajudado!
No enunciado do problema é dito que, caso o target não esteja no array, o programa retorne -1, indicando que o target não existe e portanto não pode ser encontrado. No primeiro parágrafo diz: " if target exists, then return its index. Otherwise, return -1" ou caso você não saiba inglês, "se o alvo existe, retorne seu índice. Caso contrário, retorne -1."
é uma exigência do enunciado do problema no próprio leetcode.
mas caso vc implemente por conta própria no seu próprio editor pra treinar, pode retornar uma mensagem avisando que o target não existe no array ao invés do -1.
Complementando o que a galera disse, o retorno de -1 é quase como uma "boa prática" ou convenção quando é um algoritmo de busca de índices.
Como os índices são de 0 a n, retornar -1 é como dizer que não foi encontrado sem mudar o tipo do retorno, ao invés de jogar uma excessão(erro) ou retornar um outro tipo que não seja um inteiro
Achei a thumb sensasional kkkkkkkkkk
Uma dúvida besta na prática o que um ponteiro a mais consome?
Tipo a vantagem de 1 para 2 e de 2 para 4 e assim por diante.
Imagino eu que o mais impactado seria memória.
Reduz ridiculamente o tempo de busca.
Em vez de percorrer cada item você corta pela metade o número de buscas. Numa lista de 10 itens parece bobeira, mas imagina uma lista com 10 mil itens?
@@bituca__ Fiz um teste com uma lista de 1kk de int, 1000 iterações e medi os tempos, seguem os resultados:
Tempo médio com 1 ponteiros: 0.000002 segundos
Tempo médio com 2 ponteiros: 0.000008 segundos
Tempo médio com 4 ponteiros: 0.000004 segundos
Tempo médio com 8 ponteiros: 0.000006 segundos
Tempo médio com 10 ponteiros: 0.000009 segundos
Ponteiros Tempo (s)
0 1 0.000002
1 2 0.000008
2 4 0.000004
3 8 0.000006
4 10 0.000009
Todas as vezes 1 ponteiro só foi mais rápido, talvez pelo tipo de implementação, mas os resultados foram Proximo's a esse na grande maioria dos casos.
import time
import random
import pandas as pd
import matplotlib.pyplot as plt
# Função para busca binária com 1 ponteiro (divisão clássica)
def binary_search_1_pointer(arr, target):
left, right = 0, len(arr) - 1
while left 0:
left = points[i - 1] + 1
break
else:
left = points[-1] + 1
return -1
# Função para medir o tempo de busca com múltiplas repetições
def measure_performance(search_func, arr, target, k=1, repetitions=1000):
total_time = 0
for _ in range(repetitions):
start_time = time.time()
if k == 1:
search_func(arr, target)
else:
search_func(arr, target, k)
total_time += time.time() - start_time
return total_time / repetitions
# Lista de 1.000.000 itens ordenados
arr = list(range(10000000))
# Elemento que vamos buscar
target = random.choice(arr)
# Número de ponteiros a serem testados (1, 2, 4, 8, 10)
pointer_counts = [1, 2, 4, 8, 10]
# Dicionário para armazenar os resultados de tempo
performance_results = {}
# Medir desempenho para diferentes ponteiros
for k in pointer_counts:
if k == 1:
time_taken = measure_performance(binary_search_1_pointer, arr, target)
else:
time_taken = measure_performance(binary_search_multi_pointer, arr, target, k)
performance_results[k] = time_taken
print(f"Tempo médio com {k} ponteiros: {time_taken:.6f} segundos")
# Criar um DataFrame para os resultados
df = pd.DataFrame(list(performance_results.items()), columns=["Ponteiros", "Tempo (s)"])
# Exibir o DataFrame
print(df)
# Plotar os resultados
plt.figure(figsize=(10, 6))
plt.plot(df["Ponteiros"], df["Tempo (s)"], marker='o', linestyle='-', color='b')
plt.title("Desempenho da Busca Binária com Diferentes Quantidades de Ponteiros (Média de 1000 Repetições)")
plt.xlabel("Número de Ponteiros")
plt.ylabel("Tempo (s)")
plt.grid(True)
plt.show()
@@leo1722467 Se não for incômodo, poderia compartilhar o algoritmo por favor?
@@leo1722467 Numa máquina moderna o código compila rápido mesmo. O tempo de compilação de uma binary search com 2 pointers é de O (log n), o segundo mais rápido. Com 1 pointer é O(n), o terceiro mais rápido. Olhando no gráfico, vê-se que a O(n) supera o O(log n) apenas quando a quantidade de elementos for pequena. Eu sugeriria aumentar pra 1 bilhão de itens, ou 1 tri, e comparar.
Se aumentar o número de pointers o código vai ficando lento mesmo.
"Terminei em menos de 5 minutos, então agora o merchan" [poxa, não fala mais do livro Gelego? Tem q incluir no merchan tbm]
kkkk ok ok. thumbnail foi bom
show
"glitchless". 😂
kct, o video ta em 2x KKJKJKJKJKJKJKJK
first