DEV Community: Gustavo Medeiros

Introdução a algoritmos: Pesquisa binária

Gustavo Medeiros — Tue, 17 Sep 2024 22:42:33 +0000

Introdução

Algoritmo é um conjunto de instruções que realizam uma tarefa.

Pesquisa Binária

Vamos supor que você entre no Facebook. Ao fazer isso, o Facebook precisa verificar se você tem uma conta no site. Logo, ele procura seu nome de usuário em um banco de dados. Digamos que seu usuário seja "TonyStark". O Facebook poderia começar pela letra "A" para procurar seu nome, mas faz mais sentido começar pelo meio.

Isso é um problema de busca. E todos esses casos usam um algoritmo para resolvê-lo: Pesquisa Binária.

A pesquisa binária é um algoritmo cuja entrada é uma lista ordenada de elementos. Se o elemento que você está buscando está na lista, a pesquisa binária retorna sua localização. Caso contrário, a pesquisa binária retorna None.

Nota: A pesquisa binária só funciona quando a lista está ordenada. Por exemplo, os nomes em uma agenda telefônica estão em ordem alfabética.

Vamos escrever a pesquisa binária em Python. O exemplo de código que utilizaremos aqui usa arrays. A função pesquisa_binaria recebe um array ordenado e um item. Se o item estiver no array, a função retorna sua posição. Dessa maneira, você sabe a partir de qual ponto do array deve continuar procurando. No início, o código do array segue assim:

baixo = 0
alto = len(lista) - 1

meio = (baixo + alto) // 2
chute = lista[meio]

Nota: meio será arredondado para baixo automaticamente pelo Python se (baixo + alto) não for um número par.

Se o chute for baixo, você atualizará a variável baixo proporcionalmente:

if chute < item:
    baixo = meio + 1

E se o chute for muito alto, você atualizará a variável alto. Aqui está o código completo:

def pesquisa_binaria(lista, item):
     baixo = 0
     alto = len(lista) - 1

     while baixo <= alto:
          meio = (baixo + alto) // 2
          chute = lista[meio]
          if chute == item:
              return meio
          if chute > item:
              alto = meio - 1
          else:
              baixo = meio + 1
     return None

minha_lista = [1, 3, 5, 7, 9]

print(pesquisa_binaria(minha_lista, 3)) # => 1
print(pesquisa_binaria(minha_lista, -1)) # => None

Explicação

baixo e alto acompanham a parte da lista que você está procurando;
Enquanto ainda não chegou a um único elemento, verifique o elemento central;
Encontre o item;
O chute foi muito alto;
O chute foi muito baixo;
O item não existe;
Vamos testá-lo;
Lembre-se: as listas começam no índice 0. O próximo endereço tem índice 1;
None significa nulo em Python. Ele indica que o item não foi encontrado.

Livro de referência: Para um entendimento mais profundo sobre algoritmos, recomendo o livro "Entendendo Algoritmos: Um Guia Ilustrado para Programadores e Outros Curiosos" de Aditya Y. Bhargava. Esse livro fornece explicações claras e ilustradas de diversos algoritmos, incluindo a pesquisa binária.

Problema HackerRank em Python - Base Data Types Lists

Gustavo Medeiros — Wed, 04 Sep 2024 02:54:06 +0000

Este código em Python é projetado para executar uma série de operações em uma lista com base em comandos fornecidos pelo usuário. Vamos analisar o código passo a passo para entender seu funcionamento:

if __name__ == '__main__':
    N = int(input())
    l = []
    while(N>0):
        cmd_l = input().split()
        if(len(cmd_l) == 3 and cmd_l[0] == "insert"):
            #insert statement
            l.insert(int(cmd_l[1]),int(cmd_l[2]))
        elif(len(cmd_l) == 2 and (cmd_l[0] == "remove" or cmd_l[0] == "append")):
            if(cmd_l[0] == "remove"):
                l.remove(int(cmd_l[1]))
            elif(cmd_l[0] == "append"):
                l.append(int(cmd_l[1]))
        elif(len(cmd_l) == 1):
            if(cmd_l[0] == "sort"):
                l.sort()
            elif(cmd_l[0] == "reverse"):
                l.reverse()
            elif(cmd_l[0] == "pop"):
                l.pop()                
            elif(cmd_l[0] == "print"):
                print(l)
        N -= 1

if __name__ == '__main__':

Essa linha verifica se o script está sendo executado diretamente. Pratica adotada para garantir que o código dentro deste bloco só será executado se o arquivo for o ponto de entrada do programa.

N = int(input())

O programa espera que o usuário insira um número inteiro que é armazenado na variável N. Este número representa quantas operações o usuário vai realizar.

l = []

Lista vazia l usada para armazenar os elementos conforme as operações forem sendo realizadas.

while(N>0):

Um loop while é iniciado que continuará executando enquanto N for maior que 0. isso significa que o loop executará N vezes, uma vez para cada operação que o usuário desejar realizar.

cmd_l = input().split()

Dentro do loop o programa espera que o usuário insira uma linha de texto, que é dividida em uma lista de strings (cmd_l) usando o método split(). Cada elemento da lista cmd_l representa uma parte da operação a ser realizada.

if(len(cmd_l) == 3 and cmd_l[0] == "insert"):

Esta linha verifica se a operação é um comando de "insert" com três partes (cmd_l deve ter comprimento 3 e o primeiro elemento deve ser "insert").

l.insert(int(cmd_l[1]),int(cmd_l[2]))

Se a condição acima for verdadeira, o método insert da lista l é chamado. Os argumentos são convertidos de string para inteiro: cmd_l[1] é a posição onde o elemento será inserido, e cmd_l[2] é o elemento a ser inserido.

elif(len(cmd_l) == 2 and (cmd_l[0] == "remove" or cmd_l[0] == "append")):

Esta linha verifica se a operação é um comando de "remove" ou "append" com duas partes cmd_l deve ter comprimento 2 e o primeiro elemento deve ser "remove" ou "append".

if(cmd_l[0] == "remove"): l.remove(int(cmd_l[1])) elif(cmd_l[0] == "append"): l.append(int(cmd_l[1]))

Dependendo do comando(remove ou append), o método correspondente da lista l é chamado. Para remove, o elemento cmd_l (convertido para inteiro) é removido da lista. Para append, o elemento cmd_l[[1](convertido para inteiro) é adicionado ao final da lista.

elif(len(cmd_l) == 1):

Verifica se a operação é um comando com uma única parte (cmd_l deve ter comprimento 1).

if(cmd_l[0] == "sort"): l.sort() elif(cmd_l[0] == "reverse"): l.reverse() elif(cmd_l[0] == "pop"): l.pop() elif(cmd_l[0] == "print"): print(l)

Dependendo do comando(sort, reverse, pop, ou print), o método correspondente da lista l é chamado. sort ordena a lista, reverse inverte a ordem dos elementos, pop remove o último elemento, e print imprime a lista.

N -= 1

No final do loop, N é decrementado em 1, indicando que uma operação foi realizada. Isso continua até que N seja 0, quando o loop termina.

Problema encontrado durante o primeiro uso com Node.js e React com Visual Studio Code

Gustavo Medeiros — Wed, 14 Aug 2024 18:48:32 +0000

Em algum momento, dependendo da trajetória da qual irá seguir, terá de usar Node.js e React para a criação de um projeto, seja como desenvolvedor front-end ou até como mesmo como desenvolvedor fullstack. Durante esse processo pode haver problemas simples, mas que acabam consumindo o nosso tempo.

PS C:\users\name\Desktop\exemple> npx create-react-app. npx: O termo 'npx' não é reconhecido como nome de cmlet, função, arquivo de script ou programa operável. Verifique a grafia do nome ou, se um caminho tiver sido incluído, veja se o caminho está correto e tente novamente. No linha: 1 caractere: 1 +npx create-react-app. ...

Primeiro verificar se o node.js está instalado e de preferência com a versão mais atualizado do software. Entre no seu terminal windows powershell e digite node -v

PS C:\Users\name> node -v
v20.16.0

Caso não esteja instalado o node.js entre no Site oficial. Se possuir duvidas acesse então Como instalar Node.js.

Verificar se o arquivo da instalação está no diretório PATH para executar o node.js no sistema. O PATH é onde contém os diretórios que o sistema operacional irá buscar para poder executar.

Primeiro encontre onde está o arquivo da instalação do node.js e para isso siga esse passo a passo:

Use a caixa de diálogo de pesquisa e digite por node.js
Clique Abrir local de arquivo.
Em cima do Node.js clique com o botão direito e vá em Abrir local de arquivo novamente.
Copie o caminho do arquivo na barra superior, como exemplo C:\Program Files\nodejs.

Após descobrir o caminho do seu arquivo onde está o node aplicativo, vamos abrir o diretório do PATH

Clique no ícone da área de trabalho
Clique em Configurações
Clique em Sistema
Clique em Sobre
Clique em Configurações avançadas do sistema
Clique no botão Variáveis de Ambiente...
Vá em path e clique no botão Editar...
Clique no botão Novo e cole o caminho do seu arquivo como o exemplo C:\Program Files\nodejs
clique Ok

Feito isso reinicie seu terminal e o Node.js é para funcionar normalmente. Caso ainda tenha problema com o npx create-react-app., pode apenas desinstalar npm uninstall -g create-react-app e instalar novamente npm install -g create-react-app e teste a função npx create-react-app.