%cabeçalho para todos os capítulos
%\input{cabecalho}

%\begin{document}

%Opções para o pacote listings
%\input{listingOptions}

\chapter{Busca binária, fusão e o que são as variáveis}

\begin{center}
\shabox{
  \begin{Bitemize}
    \item[]\textbf{Quais novidades veremos nesta aula?}
    \item Busca binária
    \item Fusão de duas seqüências ordenadas
    \item Diferenças entre variáveis que representam tipos primitivos\\
          e aquelas que representam tipos complexos
  \end{Bitemize}
} % \shabox
\end{center}
\bigskip

\section{Busca binária}

Nesta aula vamos ver alguns dos usos da ordenação. Um exemplo
especialmente interessante é a busca binária. Suponha que estamos
escrevendo um programa que vai guardar um grande número de informações.
Estes dados mudam pouco no tempo mas são sempre consultados. Um exemplo
típico é a lista telefônica, que tem atualização anual, mas que é
consultada várias vezes por dia no sítio da operadora. Neste caso vale a
pena ``pagar o preço'' de guardar os dados ordenados pela chave de busca
(no caso da lista, o nome do assinante). Isso torna a busca, operação
freqüente, muito mais rápida. A idéia é bem simples. Como a seqüência
está ordenada, sabemos que o item do meio deixa metade dela de cada
lado. Se, em uma primeira passagem, nós simplesmente perguntarmos qual a
posição do valor buscado com relação a esse elemento intermediário,
podemos jogar metade do trabalho fora. Há três possibilidades:

\begin{enumerate}
  \item O objeto buscado tem a mesma chave do objeto do meio: então já
        encontramos o que queríamos e nosso trabalho acabou.
  \item O objeto buscado vem antes do objeto do meio: podemos então
        concentrar a busca na porção inicial da seqüência e esquecer a
        parte do fim.
  \item O objeto buscado fica depois do objeto intermediário: a busca deve
        continuar apenas na parte final.
\end{enumerate}

Ou seja podemos, usando o elemento intermediário, eliminar metade do
trabalho a cada passo. Isso faz com que a busca fique muito mais rápida!
Vejamos com fica a implementação da busca binária para um array de
inteiros. Este código pode ser facilmente adaptado para double e cadeias
de caracteres.

\begin{lstlisting}
int buscaBinária(int valor, int[] vetor)
{
  int esq = 0,
      dir = vetor.length - 1,
      meio;

  while (esq <= dir)
  {
    meio = (esq + dir) / 2;
    if (valor > vetor[meio])
      esq = meio + 1;
    else if (valor < vetor[meio])
      dir = meio - 1;
    else
      return meio;
  }
  return -1;
}
\end{lstlisting}

\section{Fusão}

Um outro algoritmo interessante ligado a seqüências ordenadas é a fusão de
duas delas. Ou seja, a união (preservando repetições) de duas seqüências
ordenadas em uma única seqüência maior ainda em ordem. Esta operação é
conhecida como fusão.  Vejamos como podemos implementá-la:

\begin{lstlisting}
// Combinação de dois vetores ordenados em um novo vetor ordenado.
// Note que este método devolve um vetor.
int[] fusão(int []a, int b[])
{
  int posa = 0,
      posb = 0,
      posc = 0;
  int[] c = new int[a.length + b.length];

  // Enquanto nenhuma das duas seqüências está vazia...
  while(posa < a.length && posb < b.length)
  {
    // Pega o menor elemento atual entre a e b.
    if(b[posb] <= a[posa])
    {
      c[posc] = b[posb];
      posb++;
    }
    else
    {
      c[posc] = a[posa];
      posa++;
    }
    posc++;
  }
  // Completa com a seqüência que ainda não acabou.
  while (posa < a.length)
  {
    c[posc] = a[posa];
    posc++;
    posa++;
  }
  while (posb < b.length)
  {
    c[posc] = b[posb];
    posb++;
    posc++;
  }

  return c;
}
\end{lstlisting}

\section{O que guardam as variáveis?}

Em primeiro lugar, vamos usar o nome variável para designar qualquer
nome associado a dados em um programa. Isso inclui os atributos de
objetos, parâmetros de métodos e variáveis locais. Em Java, uma variável
associada a um tipo primitivo 
(\texttt{int}, \texttt{double}, \texttt{boolean} e \texttt{char})
tem um comportamento levemente diferente de variáveis associadas a objetos
complexos (String, arrays, objetos pertencentes a classes definidas pelo
programador, etc.) Vamos tentar explicar as diferenças usando a forma
como o Java armazena os dados. Os dados de tipo primitivo são todos
muito simples, ocupando pouco espaço de memória. Neste caso vale a pena
guardar nessas variáveis o seu valor. Logo, se \texttt{a} e \texttt{b} são variáveis
de mesmo tipo primitivo, a operação \texttt{a = b} copia em \texttt{a} o valor que já
está em \texttt{b}. Isso explica porque a mudança em um parâmetro de tipo
primitivo dentro de métodos não se reflete fora. O parâmetro alterado
não tem nenhuma ligação com a variável que estava em seu lugar na
chamada além da cópia inicial do seu valor. 

Já para objetos complexos, como cadeias de caracteres, arrays e qualquer
objeto de uma classe definida pelo programador, a situação é bem diferente.
Estes objetos podem ser muito complicados, ocupando muito espaço de memória.
Neste caso o Java não guarda nas variáveis uma cópia do objeto, mas
simplesmente a posição na memória na qual este objeto está armazenado. Por
este motivo, fala-se que em Java as variáveis associadas a objetos complexos
são \emph{referências} para estes objetos. No momento que o objeto precisa ser
usado, Java o localiza a partir de uma referência para ele armazenada em uma
variável. Esta pequena diferença gera algumas surpresas. Considere que temos
uma classe chamada \texttt{Fruta} com um atributo \texttt{preço} e
métodos \texttt{carregaPreço} e \texttt{imprimePreço}.  O que ocorre quando
executamos o seguinte código?

\begin{lstlisting}
Fruta a = new Fruta();
a.carregaPreço(10);
Fruta b = a;
b.carregaPreço(100);
a.imprimePreço();
\end{lstlisting}

Observamos que o preço da fruta \texttt{a} mudou. Isto ocorreu porque
\texttt{a} e \texttt{b} são referências para um mesmo objeto na memória. Como
dois apelidos para mesma pessoa. Qualquer coisa que ocorre com um objeto
usando um de seus apelidos se reflete para a visão do outro apelido. Esse
raciocínio explica porque alterações em objetos complexos dentro de um método
se propagam para fora. O parâmetro associado a esse objeto é também um
apelido.



\section{Exercícios}

\begin{enumerate}

  \item Implemente o algoritmo de busca ternária, que funciona de forma
  similar ao de busca binária mas que divide o vetor em três partes iguais a
  cada iteração.

  \item Construa um programa que lhe auxilie a determinar qual algoritmo é
  mais eficiente: a busca binária ou a busca ternária.
\end{enumerate}