Please enable JavaScript.
Coggle requires JavaScript to display documents.
Decrease-by-a-Constant-Factor - Coggle Diagram
Decrease-by-a-Constant-Factor
Examples
Binary Search
Dado um vetor ordenado, compara-se o elemento central desse vetor com o número que se quer encontrar
Se forem iguais, o algoritmo para. Já se o número fornecido for maior, a operação é repetida recursivamente com a parte que sobrou do vetor até que o número seja encontrado
Algoritmo
Implements nonrecursive binary search
Input: An array A[0..n − 1] sorted in ascending order and
a search key K
Output: An index of the array’s element that is equal to K
or −1 if there is no such element
l ← 0; r ← n − 1
while l ≤ r do
if n%2 <-- 0 m ← (l + r)/2
if K = A[m]return m
else if K<A[m] r ← m − 1
else l ← m + 1
return −1
else m <-- (l + r - 1)/2
Fake Coin Problem
O problema consiste em n moedas diferentes, na qual uma delas é falsa (no exemplo a seguir, a moeda falsa é a mais leve)
Como detectar a moeda falsa de modo eficiente?
Dividir as n moedas em duas pilhas de n/2 moedas cada, deixando uma de fora caso n seja ímpar
Colocar as duas pilhas na balança. Se as duas pilhas tiverem o mesmo peso, a moeda deixada de fora será a falsa. Já se isso não ocorrer, a pilha que tiver mais leve terá a moeda falsa. Assim, pode-se aplicar esse algoritmo recursivamente, até a moeda falsa ser deixada de fora ou ser a última da pilha.