Você está aqui: Python ::: Dicas & Truques ::: Ordenação e Pesquisa (Busca)

Como usar a busca binária em Python - Pesquisa binária na linguagem Python

Quantidade de visualizações: 566 vezes
A busca binária, ou pesquisa binária, é um algoritmo eficiente para encontrar um item em uma lista (vetor ou array) ordenada. Sim, os itens devem, obrigatoriamente, estar ordenados.

O processo é bem simples. A busca binária começa a partir do meio da lista e compara o item nesta posição com o valor sendo pesquisado. Se o valor não for encontrado e for menor que o item no meio da lista, o algoritmo passa para a porção à esquerda da lista, eliminando, assim, metade dos elementos do vetor ou array (a porção maior que o valor pesquisado).

Se o valor não for encontrado e for maior que o item no meio da lista, então a busca reinicia a partir da metade da sub-lista à direita (os itens maiores que o valor pesquisado). Essa divisão continua até que o valor seja encontrado ou não seja mais possível dividir a lista pela metade.

Se um array ou vetor possuir 100 elementos e usarmos a busca binária nele, precisaremos efetuar no máximo 7 tentativas para encontrar o valor desejado. Se a lista possuir 4 bilhões de itens nós teremos que fazer no máximo 32 tentativas.

Isso acontece porque a pesquisa binária é executada em tempo logarítmico, ou seja, log2 n, onde n é a quantidade de itens no vetor. Dessa forma, se tivemos 1.000 itens em um array, log2 1000 = 10 tentativas. Lembre-se de que, na programação log e log2 retornam resultados diferentes: log(10) = 2.302585092994046 enquanto log2(10) = 3.321928094887362. Na análise da busca binária nós usamos sempre log2.

Vamos agora ver como podemos codificar a busca binária em Python. Veja o código a seguir:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

# função principal do programa
def main():
  # vamos criar uma lista ordenada de inteiros
  valores = [3, 5, 7, 8, 9, 12, 43, 50, 52, 60]
  print("Os valores da lista são: {0}".format(valores))

  # vamos pedir o item a ser pesquisado
  numero = int(input("Informe o número a ser pesquisado: "))

  # agora vamos pesquisar o número no array usando a pesquisa
  # binária
  # a variável esquerda aponta para o primeiro elemento do vetor
  esquerda = 0
  # a variável direita aponta para o último elemento do vetor
  direita = len(valores) - 1
  # para indicar se o valor foi encontrado
  encontrado = False

  # enquanto houver mais de um elemento a ser comparado
  while esquerda <= direita:
    # obtemos o elemento na metade da lista
    meio = (esquerda + direita) // 2
    
    # fazemos a comparação
    if numero == valores[meio]:
      print("O número foi encontrado no índice {0}".format(
        meio))
      encontrado = True
      break # sai do laço  

    # o item atual é maior que o valor pesquisado?
    if valores[meio] > numero:
      direita = meio - 1
    # o item atual é menor que o valor pesquisado?
    else:
      esquerda = meio + 1

  # o valor foi encontrado?
  if not encontrado:
    print("O valor pesquisado não foi encontrado")  

if __name__== "__main__":
  main()

Ao executar este código Python nós teremos o seguinte resultado:

Os valores da lista são: [3, 5, 7, 8, 9, 12, 43, 50, 52, 60]
Informe o número a ser pesquisado: 9
O número foi encontrado no índice 4

Link para compartilhar na Internet ou com seus amigos:

Python ::: NumPy Python Library (Biblioteca Python NumPy) ::: Arrays e Matrix (Vetores e Matrizes)

Como repetir os elementos de um vetor ou matriz usando a função repeat() da NumPy do Python

Quantidade de visualizações: 823 vezes
A função repeat() da biblioteca NumPy do Python é usada quando queremos repetir os elementos de um vetor ou matriz um determinado número de vezes. Em sua forma mais simples esta função pede um array e um número inteiro indicando a quantidade de repetições.

Veja o código Python completo para o exemplo:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

# vamos importar a biblioteca NumPy
import numpy as np

def main():
  # vamos criar um vetor contendo 5 elementos
  vetor = np.array([5, 3, 9, 1, 4])

  # agora vamos aplicar a função repeat() a este vetor
  novo_vetor = np.repeat(vetor, 3)

  # vamos mostrar o resultado
  print("O vetor original é: {0}".format(vetor))
  print("O novo vetor é: {0}".format(novo_vetor))

if __name__== "__main__":
  main()

Ao executar este código Python nós teremos o seguinte resultado:

O vetor original é: [5 3 9 1 4]
O novo vetor é: [5 5 5 3 3 3 9 9 9 1 1 1 4 4 4]

Veja agora o efeito desta função em uma matriz de 2 linhas por 3 colunas:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

# vamos importar a biblioteca NumPy
import numpy as np

def main():
  # vamos criar uma matriz de 2 linhas e 3 colunas
  matriz = np.array([(1, 2, 3), (4, 5, 6)])

  # agora vamos aplicar a função repeat() a esta matriz
  nova_matriz = np.repeat(matriz, 3, 0)

  # vamos mostrar o resultado
  print("A matriz original é:\n\n{0}".format(matriz))
  print("A nova matriz é:\n\n{0}".format(nova_matriz))

if __name__== "__main__":
  main()

Note que informei o valor 0 para o terceiro parâmetro da função repeat(). Isso faz com que os elementos da matriz sejam repetidos no eixo x. Veja:

A matriz original é:

[[1 2 3]
 [4 5 6]]

A nova matriz é:

[[1 2 3]
 [1 2 3]
 [1 2 3]
 [4 5 6]
 [4 5 6]
 [4 5 6]]


Se trocarmos o valor 0 por 1, o resultado será:

A matriz original é:

[[1 2 3]
 [4 5 6]]

A nova matriz é:

[[1 1 1 2 2 2 3 3 3]
 [4 4 4 5 5 5 6 6 6]]



Python ::: Desafios e Lista de Exercícios Resolvidos ::: Arrays e Matrix (Vetores e Matrizes)

Exercícios Resolvidos de Python - Escreva um programa Python para mover todos os zeros para o final do vetor, sem alterar a ordem dos elementos já presentes no array

Quantidade de visualizações: 1742 vezes
Pergunta/Tarefa:

Dado o seguinte vetor de inteiros:

# vamos declarar e construir um vetor de 8 inteiros
valores = [0, 3, 0, 5, 7, 4, 0, 9]
Escreva um programa Python para mover todos os zeros para o final do vetor, ou seja, para a direita, sem alterar a ordem dos elementos diferentes de zero já presentes no array e sem criar um vetor adicional ou temporário.

Sua saída deverá ser parecida com:

Vetor na ordem original:

0   3   0   5   7   4   0   9   

Vetor com os zeros deslocados para o final:

3   5   7   4   9   0   0   0
Resposta/Solução:

Veja a resolução comentada deste exercício usando Python:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

# método principal
def main():
  # vamos declarar e construir um vetor de 8 inteiros
  valores = [0, 3, 0, 5, 7, 4, 0, 9]
    
  # vamos mostrar o vetor na ordem original
  print("Vetor na ordem original:\n")
  for i in range(len(valores)):
    print("%d   " % valores[i], end="")
    
  # vamos inicializar j como 0 para que ele aponte para
  # o primeiro elemento do vetor
  j = 0
    
  # agora o laço for percorre todos os elementos do vetor,
  # incrementanto a variável i e deixando o j em 0
  for i in range(len(valores)):
    # encontramos um valor que não é 0
    if(valores[i] != 0):
      # fazemos a troca entre os elementos nos índices
      # i e j
      temp = valores[i]
      valores[i] = valores[j]
      valores[j] = temp
      # e avançamos o j para o elemento seguinte
      j = j + 1
    
  # agora mostramos o resultado
  print("\n\nVetor com os zeros deslocados para o final:\n")
  for i in range(len(valores)):
    print("%d   " % valores[i], end="")
    
if __name__== "__main__":
  main()

Não se esqueça: A resolução do exercício deve ser feita sem a criação de um vetor, array ou lista adicional, e os elementos diferentes de zero devem permanecer na mesma ordem que eles estavam antes.


Python ::: Dicas & Truques ::: Data e Hora

Como exibir a data atual em Python de acordo com as configurações regionais usando as funções strftime() e setlocale()

Quantidade de visualizações: 7599 vezes
Nesta dica mostrarei como podemos combinar os objeto datetime e locale e as funções today(), strftime() e setlocale() para retornar e exibir a data atual em Python usando as configurações regionais do computador do usuário.

Veja o código completo para o exemplo:

----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------

from datetime import datetime
import locale

# função principal do programa
def main():
  # Configurações do usuário
  locale.setlocale(locale.LC_ALL, "")

  # Obtém um datetime da data e hora atual
  hoje = datetime.today()

  # Exibe a data atual
  print("Hoje é {0}".format(hoje.strftime("%x")))

if __name__== "__main__":
  main()

Ao executar este código Python nós teremos o seguinte resultado:

Hoje é 04/02/2023


Desafios, Exercícios e Algoritmos Resolvidos de Python

Veja mais Dicas e truques de Python

Dicas e truques de outras linguagens

Códigos Fonte

Programa de Gestão Financeira Controle de Contas a Pagar e a Receber com Cadastro de Clientes e FornecedoresSoftware de Gestão Financeira com código fonte em PHP, MySQL, Bootstrap, jQuery - Inclui cadastro de clientes, fornecedores e ticket de atendimento
Diga adeus às planilhas do Excel e tenha 100% de controle sobre suas contas a pagar e a receber, gestão de receitas e despesas, cadastro de clientes e fornecedores com fotos e histórico de atendimentos. Código fonte completo e funcional, com instruções para instalação e configuração do banco de dados MySQL. Fácil de modificar e adicionar novas funcionalidades. Clique aqui e saiba mais
Controle de Estoque completo com código fonte em PHP, MySQL, Bootstrap, jQuery - 100% funcional e fácil de modificar e implementar novas funcionalidadesControle de Estoque completo com código fonte em PHP, MySQL, Bootstrap, jQuery - 100% funcional e fácil de modificar e implementar novas funcionalidades
Tenha o seu próprio sistema de controle de estoque web. com cadastro de produtos, categorias, fornecedores, entradas e saídas de produtos, com relatórios por data, margem de lucro e muito mais. Código simples e fácil de modificar. Acompanha instruções para instalação e criação do banco de dados MySQL. Clique aqui e saiba mais

Linguagens Mais Populares

1º lugar: Java
2º lugar: Python
3º lugar: C#
4º lugar: PHP
5º lugar: C
6º lugar: Delphi
7º lugar: JavaScript
8º lugar: C++
9º lugar: VB.NET
10º lugar: Ruby



© 2025 Arquivo de Códigos - Todos os direitos reservados
Neste momento há 75 usuários muito felizes estudando em nosso site.