13.Buscas Sequêncial e Binárias.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "toc": true
   },
   "source": [
    "<h1>Table of Contents<span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\" style=\"margin-top: 1em;\"><ul class=\"toc-item\"><li><span><a href=\"#Busca-Sequêncial-e-Binárias\" data-toc-modified-id=\"Busca-Sequêncial-e-Binárias-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Busca Sequêncial e Binárias</a></span><ul class=\"toc-item\"><li><span><a href=\"#Busca-pelo-Mínimo\" data-toc-modified-id=\"Busca-pelo-Mínimo-1.1\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Busca pelo Mínimo</a></span></li><li><span><a href=\"#Busca-Linear-ou-Sequencial\" data-toc-modified-id=\"Busca-Linear-ou-Sequencial-1.2\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>Busca Linear ou Sequencial</a></span></li><li><span><a href=\"#Exercícios\" data-toc-modified-id=\"Exercícios-1.3\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>Exercícios</a></span><ul class=\"toc-item\"><li><span><a href=\"#Discuta-a-seguinte-versão-da-função-buscaSequencial\" data-toc-modified-id=\"Discuta-a-seguinte-versão-da-função-buscaSequencial-1.3.1\"><span class=\"toc-item-num\">1.3.1&nbsp;&nbsp;</span>Discuta a seguinte versão da função buscaSequencial</a></span></li><li><span><a href=\"#Critique-a-seguinte-versão-da-função-buscaSequencial\" data-toc-modified-id=\"Critique-a-seguinte-versão-da-função-buscaSequencial-1.3.2\"><span class=\"toc-item-num\">1.3.2&nbsp;&nbsp;</span>Critique a seguinte versão da função buscaSequencial</a></span></li><li><span><a href=\"#Discuta-a-seguinte-versão-recursiva-da-função-buscaSequencial\" data-toc-modified-id=\"Discuta-a-seguinte-versão-recursiva-da-função-buscaSequencial-1.3.3\"><span class=\"toc-item-num\">1.3.3&nbsp;&nbsp;</span>Discuta a seguinte versão recursiva da função buscaSequencial</a></span></li></ul></li></ul></li><li><span><a href=\"#Busca-Binária-em-uma-Lista\" data-toc-modified-id=\"Busca-Binária-em-uma-Lista-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>Busca Binária em uma Lista</a></span></li><li><span><a href=\"#Versão-recursiva-da-busca-binária\" data-toc-modified-id=\"Versão-recursiva-da-busca-binária-3\"><span class=\"toc-item-num\">3&nbsp;&nbsp;</span>Versão recursiva da busca binária</a></span></li><li><span><a href=\"#Exercícios-de-Busca-Binária\" data-toc-modified-id=\"Exercícios-de-Busca-Binária-4\"><span class=\"toc-item-num\">4&nbsp;&nbsp;</span>Exercícios de Busca Binária</a></span><ul class=\"toc-item\"><li><span><a href=\"#A-seguinte-implementação-da-busca-binária-funciona-corretamente?\" data-toc-modified-id=\"A-seguinte-implementação-da-busca-binária-funciona-corretamente?-4.1\"><span class=\"toc-item-num\">4.1&nbsp;&nbsp;</span>A seguinte implementação da busca binária funciona corretamente?</a></span></li><li><span><a href=\"#A-seguinte-versão-de-buscaBinaria-está-correta?\" data-toc-modified-id=\"A-seguinte-versão-de-buscaBinaria-está-correta?-4.2\"><span class=\"toc-item-num\">4.2&nbsp;&nbsp;</span>A seguinte versão de buscaBinaria está correta?</a></span></li><li><span><a href=\"#Critique-a-seguinte-versão-da-função-bb\" data-toc-modified-id=\"Critique-a-seguinte-versão-da-função-bb-4.3\"><span class=\"toc-item-num\">4.3&nbsp;&nbsp;</span>Critique a seguinte versão da função <code>bb</code></a></span></li><li><span><a href=\"#Consumo-de-tempo\" data-toc-modified-id=\"Consumo-de-tempo-4.4\"><span class=\"toc-item-num\">4.4&nbsp;&nbsp;</span>Consumo de tempo</a></span></li></ul></li><li><span><a href=\"#Exercício-com-chaves-repetidas\" data-toc-modified-id=\"Exercício-com-chaves-repetidas-5\"><span class=\"toc-item-num\">5&nbsp;&nbsp;</span>Exercício com chaves repetidas</a></span></li><li><span><a href=\"#Exercício-Two-Sum\" data-toc-modified-id=\"Exercício-Two-Sum-6\"><span class=\"toc-item-num\">6&nbsp;&nbsp;</span>Exercício Two Sum</a></span></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Busca Sequêncial e Binárias\n",
    "\n",
    "Um algoritmo de busca é um método para encontrar um item ou grupo de itens com propriedades específicas dentro de uma coleção de itens. Nós nos referimos à coleção de itens como um espaço de pesquisa. O espaço de busca pode ser algo concreto, como um conjunto de registros médicos, ou algo abstrato, como o conjunto de números inteiros. Um grande número de problemas que ocorrem na prática podem ser formulados como problemas de busca."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Vamos estudar dois algoritmos comumente usados em buscas. Em primeiro lugar, discutiremos o projeto do algoritmo, mostramos sua implementação como uma função de Python e, finalmente, fornecemos uma análise da complexidade computacional do mesmo. Para manter as coisas simples, as funções de busca irão processar uma lista de números inteiros. Listas de diferentes tamanhos podem ser passadas como parâmetros para as mesmas. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Busca pelo Mínimo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "A função `min` de Python retorna o item mínimo ou menor em uma lista. Para estudar a complexidade desse algoritmo, vamos desenvolver uma versão alternativa que retorna a posição do item mínimo. O algoritmo assume que a lista não está vazia e que os itens estão em ordem arbitrária. O algoritmo começa tratando a primeira posição como a do item mínimo. Em seguida, procura à direita por um item menor e, se for encontrado, restabelece a posição do item mínimo para a posição atual. Quando o algoritmo atinge o final da lista, ele retorna a posição do item mínimo. Eis o código do algoritmo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def ourMin(lst):\n",
    "    \"\"\"Returns the position of the minimum item.\"\"\"\n",
    "    minpos = 0\n",
    "    current = 1\n",
    "    while current < len(lst):\n",
    "        if lst[current] < lst[minpos]:\n",
    "            minpos = current\n",
    "        current += 1\n",
    "    return minpos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "ourMin([3, 4, 8, 1, 9, 2, 7, 6])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Como você pode ver, há três instruções fora do laço que executam o mesmo número de vezes, independentemente do tamanho da lista. Assim, podemos descontá-los. Dentro do laço, encontramos mais três instruções. Destes, a comparação na instrução \\textbf{if} e o incremento de execução atual em cada passagem pelo laço. Não há laços aninhados nestas instruções. Este algoritmo deve visitar todos os itens da lista para garantir que localizou a posição do item mínimo. Assim, o algoritmo deve fazer $n-1$ comparações para uma lista de tamanho $n$. Portanto, a complexidade do algoritmo é $\\large{O}$($n$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Busca Linear ou Sequencial"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "O operador `in` de Python procura por um item específico (vamos chamá-lo de item chave ou apenas chave) dentro de uma lista de itens organizados de forma arbitraria. Nessa lista, a única maneira de procurar um item de destino é começar com o item na primeira posição e compará-lo com a chave. Se os itens forem iguais, o método retornará `True`. Caso contrário, o método passa para a próxima posição e compara os itens novamente. Se o método chegar na última posição e ainda não encontrar a chave, ele retorna `False`. Esse tipo de pesquisa é chamado de busca seqüencial ou de busca linear. Uma função de pesquisa linear mais útil retornaria o índice de uma chave se for encontrado, ou -1 caso contrário. Aqui está o código Python para uma função de busca linear:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def linearSearch(key, lst):\n",
    "    \"\"\"Returns the position of the key item if found,\n",
    "       or -1 otherwise.\"\"\"\n",
    "    position = 0\n",
    "    while position < len(lst):\n",
    "        if key == lst[position]:\n",
    "            return position\n",
    "        position += 1\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "linearSearch(3, [1, 5, 8, 2, 9, 3, 6, 4, 0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Exercícios"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Discuta a seguinte versão da função buscaSequencial"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [],
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def buscaSequencial(key, vet):\n",
    "    n = len(vet)\n",
    "    for i in range(n):\n",
    "        if key == vet[i]:\n",
    "            break     \n",
    "    if i < n and vet[i] == key:\n",
    "        return i\n",
    "    else:\n",
    "        return -1\n",
    "\n",
    "print(buscaSequencial(3, [2, 4, 1, 9, 5, 3, 6]))\n",
    "print(buscaSequencial(3, [2, 4, 1, 9, 5, 8, 8]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "###  Critique a seguinte versão da função buscaSequencial"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [],
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def busca(key, vet):\n",
    "    n = len(vet) - 1\n",
    "    i = 0\n",
    "    while i < n and vet[i] != key:\n",
    "        i += 1\n",
    "    if vet[i] == key:\n",
    "        return i\n",
    "    else:\n",
    "        return -1\n",
    "\n",
    "print(busca(3, [2, 4, 1, 9, 5, 3, 6]))\n",
    "print(busca(3, [2, 4, 1, 9, 5, 8, 3]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Discuta a seguinte versão recursiva da função buscaSequencial"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def buscaR(key, idx, vet):\n",
    "    if idx < 0:\n",
    "        return -1\n",
    "    if key == vet[idx]:\n",
    "        return idx\n",
    "    return buscaR(key, idx-1, vet)\n",
    "\n",
    "lista = [2, 4, 1, 9, 5, 3, 6]\n",
    "print(buscaR(3, len(lista) - 1, lista))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Busca Binária em uma Lista\n",
    "\n",
    "A busca linear é necessária para dados que não estão organizados em uma ordem específica. Ao pesquisar dados ordenados, podemos usar uma pesquisa binária."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Para entender como uma pesquisa binária funciona, pense no que acontece quando você procura uma palavra em um dicionário. Os dados em um dicionário estão organizados em ordem alfabética, então você não faz uma pesquisa sequencial. Em vez disso, você estima a posição alfabética da palavra que você deseja encontrar no dicionário e abre o livro o mais próximo possível dessa posição. Depois de abrir o livro, você determina se a palavra em questão reside, em termos alfabéticos, em uma página anterior ou na página posterior, e volta a pesquisar as páginas conforme necessário. Você repete esse processo até encontrar a palavra."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Agora vamos considerar um exemplo de uma pesquisa binária em Python. Para começar, vamos assumir que os itens da nossa lista de números estão classificados em ordem crescente. O algoritmo de busca vai diretamente para a posição intermediária na lista e compara o item nessa posição com a chave. Se houver uma correspondência, o algoritmo retorna a posição. Caso contrário, se a chave for menor do que o item atual, o algoritmo busca a parte da lista antes da posição intermediária. Se a chave for maior que o item atual, o algoritmo busca a parte da lista após a posição do meio. O processo de busca pára quando a chave é encontrado ou a posição de início atual é maior que a posição final atual."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Aqui está o código para a função de busca binária:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def binarySearch(key, lst):\n",
    "    left, right = 0, len(lst) - 1\n",
    "    while left <= right:\n",
    "        midpoint = (left + right) // 2\n",
    "        if key == lst[midpoint]:\n",
    "            return midpoint\n",
    "        elif key < lst[midpoint]:\n",
    "            right = midpoint - 1\n",
    "        else:\n",
    "            left = midpoint + 1\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "from random import randint\n",
    "\n",
    "lst = [x * 2 for x in range(50)]\n",
    "key = randint(0, 100)\n",
    "print(key)\n",
    "binarySearch(key, lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Há apenas um laço sem laços aninhados. Mais uma vez, o pior caso ocorre quando a chave não está na lista. Quantas vezes o laço é executado neste caso? Iste será igual ao número de vezes que o tamanho da lista pode ser dividido por $2$ até o quociente ser $1$. Para uma lista de tamanho $n$, você essencialmente realiza a redução $n/2$ $/2$ . . . $/2$ até que o resultado seja $1$. Seja $k$ o número de vezes que dividimos $n$ por $2$. Para resolver $k$, você tem $n/2^k = 1$, então $n = 2^k$ e $k = log_{2}n$. Assim, a complexidade do pior caso da pesquisa binária é $\\large{O}$ ($log_{2}n$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "No exemplo abaixo:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "![Bsearch](img/bsearch.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "são necessários $3$ comparações para encontrar o número $57$, enquanto na busca sequencial são necessários $5$ comparações. Esse algoritmo funciona melhor à medida que o tamanho do problema aumenta. Nossa lista de $15$ itens requer no máximo $4$ comparações, enquanto que uma lista de $1.000.000$ de itens requer, no máximo, apenas $20$ comparações!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Versão recursiva da busca binária"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Para formular uma versão recursiva da busca binária é preciso generalizar ligeiramente o problema, trocando  `vet[0..n-1]`  por  `vet[e..d]`.  Para estabelecer uma ponte entre a formulação original e a generalizada, vamos usar uma função-embalagem (*wrapper-function*) buscaBinaria, que repassa o serviço para a função recursiva bb."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def BuscaBinaria(key, vet):\n",
    "    # Esta função recebe uma chave key e um vetor\n",
    "    # crescente vet[0..n-1] e devolve um índice m\n",
    "    # em 0..n-1 tal que v[m] == key. Se tal m\n",
    "    # não existe, devolve -1.\n",
    "    return bb(key, 0, len(vet)-1, vet)\n",
    "\n",
    "\n",
    "def bb(key, e, d, vet):\n",
    "    # Esta função recebe uma chave key e um vetor\n",
    "    # crescente vet[e..d] e devolve um índice m\n",
    "    # em e..d tal que v[m] == key. Se tal m\n",
    "    # não existe, devolve -1.\n",
    "    if e > d:\n",
    "        return -1\n",
    "    else:\n",
    "        m = (e + d) // 2\n",
    "        if vet[m] == key:\n",
    "            return m\n",
    "        elif vet[m] < key:\n",
    "            return bb(key, m+1, d, vet)\n",
    "        else:\n",
    "            return bb(key, e, m-1, vet)\n",
    "\n",
    "\n",
    "print(BuscaBinaria(3, [3, 3]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Exercícios de Busca Binária\n",
    "\n",
    "Implementações de busca binária exigem cuidado e atenção aos detalhes. É muito fácil escrever uma implementação que dá respostas erradas ou entra em loop.  Os exercícios abaixo discutem versões alternativas da função `buscaBinaria`, diferentes da que examinamos acima. Todas procuram encontrar `key` em vet[0..n-1]. Todas produzem (ou deveriam produzir) um índice `m` em `0..n` tal que `vet[j-1] < key ≤ vet[j]`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## A seguinte implementação da busca binária funciona corretamente? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def buscaB(key, vet):\n",
    "    e, d = -1, len(vet)\n",
    "    while e < (d - 1):\n",
    "        m = (e + d) // 2\n",
    "        if key == vet[m]:\n",
    "            return m\n",
    "        if key > vet[m]:\n",
    "            e = m\n",
    "        else:\n",
    "            d = m\n",
    "    return -1\n",
    "\n",
    "\n",
    "lista = [1, 2, 3, 4, 5, 6, 7, 8]\n",
    "print(buscaB(9, lista))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "O que acontece se trocarmos `while e < d-1:` por `while e < d:` ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Respostas: (a) Sim; (b) Fica em loop para key > max(vet)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## A seguinte versão de buscaBinaria está correta?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def BinarySearch(key, vet):\n",
    "    e, d = 0, len(vet)\n",
    "    while e < d:              # vet[e-1] < key <= vet[d]\n",
    "        m = (e + d) // 2 \n",
    "        if vet[m] < key:\n",
    "            e = m + 1\n",
    "        else:\n",
    "            d = m\n",
    "    return d;                 # e == d\n",
    "\n",
    "print(BinarySearch(3,[1,2,3,4]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Resposta: Não. Retorna 0 para key < min(vet) e retorna indice = len(vet) para key > max(vet)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Critique a seguinte versão da função `bb`\n",
    "\n",
    "A função recebe uma chave `key` e um vetor crescente `vet[e..d]` tal que `e ≤ d` e promete devolver um índice `m` em `e..d` tal que `vet[m] == key` (ou -1, se tal `m` não existe)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def bb (key, e, d, vet):\n",
    "    if e <= d:\n",
    "        if e == d and vet[d] == key:\n",
    "            return d\n",
    "        else:\n",
    "            return -1\n",
    "    m = (e + d) // 2\n",
    "    if vet[m] == key:\n",
    "        return m;\n",
    "    elif vet[m] < key:\n",
    "        return bb(key, m+1, d, vet)\n",
    "    else:\n",
    "        return bb(key, e, m-1, vet)\n",
    "    \n",
    "print(bb(3, 0, 4, [1, 2, 3, 4, 5]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Resposta: Fica em loop para key < min(vet)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Consumo de tempo\n",
    "Suponha que o vetor `vet` tem 511 elementos e que `key` não está no vetor.  Quantas vezes, exatamente, a função buscaBinaria comparará `key` com um elemento do vetor?  Suponha agora que o vetor `vet` tem 50000 elementos e que `key` não está no vetor.  Quantas vezes, aproximadamente, a função buscaBinaria comparará `key` com um elemento do vetor?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "k, tal que n / 2^k = 1 ou k = log2(n) = log2(511) = 9\n",
    "log2(50000) ~= 15"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "# Exercício com chaves repetidas\n",
    "Refaça as funções de busca sequencial e busca binária assumindo que a lista possui chaves que podem aparecer repetidas. Neste caso, você deve retornar uma lista com todas as posições onde a chave foi encontrada. Se a chave só aparece uma vez, a lista conterá apenas um indice. E se a chave não aparece, as funções devem retornar a lista vazia."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": []
   },
   "outputs": [],
   "source": [
    "from random import randint\n",
    "\n",
    "def linearMultipleSearch(key, lst):\n",
    "    \"\"\"Returns a list of positions of the key item\n",
    "       if found, or [] otherwise.\"\"\"\n",
    "    result = []\n",
    "    position = 0\n",
    "    while position < len(lst):\n",
    "        if key == lst[position]:\n",
    "            result.append(position)\n",
    "        position += 1\n",
    "    return result\n",
    "\n",
    "vet = [randint(0, 10) for _ in range(20)]\n",
    "print(vet)\n",
    "t = randint(0, 12)\n",
    "print(t)\n",
    "print(linearMultipleSearch(t, vet))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": []
   },
   "outputs": [],
   "source": [
    "from random import randint\n",
    "\n",
    "\n",
    "def binaryMultipleSearch(key, lst):\n",
    "    left, right = 0, len(lst) - 1\n",
    "    while left <= right:\n",
    "        midpoint = (left + right) // 2\n",
    "        if key == lst[midpoint]:\n",
    "            result = [midpoint]\n",
    "            m = midpoint - 1\n",
    "            while m >= 0 and lst[m] == key:\n",
    "                result.insert(0,m)\n",
    "                m -= 1\n",
    "            m = midpoint + 1\n",
    "            while m < len(lst) and lst[m] == key:\n",
    "                result.append(m)\n",
    "                m += 1\n",
    "            return result\n",
    "        elif key < lst[midpoint]:\n",
    "            right = midpoint - 1\n",
    "        else:\n",
    "            left = midpoint + 1\n",
    "    return []\n",
    "\n",
    "\n",
    "vet = sorted([randint(0, 20) for _ in range(20)])\n",
    "print(vet)\n",
    "t = randint(0, 25)\n",
    "print(t)\n",
    "print(binaryMultipleSearch(t, vet))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercício Two Sum\n",
    "Escreva um algoritmo eficiente para o seguinte problema:  dados um vetor crescente `v[0..n-1]` de números inteiros e um número inteiro `t`, encontrar dois índices distintos `i` e `j` tais que  `v[i] + v[j] = t`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": []
   },
   "outputs": [],
   "source": [
    "from random import randint\n",
    "\n",
    "\n",
    "def bb(key, e, d, vet):\n",
    "    if e > d:\n",
    "        return -1\n",
    "    else:\n",
    "        m = (e + d) // 2\n",
    "        if vet[m] == key:\n",
    "            return m\n",
    "        elif vet[m] < key:\n",
    "            return bb(key, m+1, d, vet)\n",
    "        else:\n",
    "            return bb(key, e, m-1, vet)\n",
    "\n",
    "\n",
    "def twoSum(t, vet):\n",
    "    res = []\n",
    "    n = len(vet)\n",
    "    for i in range(n):\n",
    "        ivalue = vet[i]\n",
    "        jvalue = t - ivalue\n",
    "        if jvalue <= ivalue:\n",
    "            e, d = 0, i\n",
    "        else:\n",
    "            e, d = i, n-1\n",
    "        j = bb(jvalue, e, d, vet)\n",
    "        if j != -1:\n",
    "            if (j, i) in res:\n",
    "                break\n",
    "            else:\n",
    "                res.append((i, j))\n",
    "    return res\n",
    "\n",
    "\n",
    "vet = sorted({randint(0, 100) for _ in range(50)})\n",
    "print(vet)\n",
    "t = randint(0, 150)\n",
    "print(t)\n",
    "print(twoSum(t, vet))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "livereveal": {
   "theme": "solarized",
   "transition": "slide"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "toc_cell": true,
   "toc_position": {},
   "toc_section_display": "block",
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}