Binary Search
Conceito Abstrato
Binary Search é um algoritmo de busca onde você tem um array explicitamente ou implicitamente ordenado, de modo que você possa fazer uma decisão binária para reduzir o conjunto de elementos onde o valor que você esteja procurando possa estar.
É um algoritmo O (log N), pois a cada execução, o conjunto de valores em que o elemento que você está procurando se encontra é reduzido pela metade, até você encontrar o valor.
Se você já procurou uma palavra em um dicionário, você já utilizou binary search na vida real.
Você pode usar binary search toda vez que você for fazer uma decisão binária para reduzir um conjunto de elementos onde você irá fazer uma busca.
Array Explicitamente Ordenado
Dado um array ordenado, ache um número e retorne o seu índice. Caso não encontre o número, retorne -1.
O conceito é bem simples, nós checamos o número que está na metade do conjunto de elementos do array que estamos checando, nesse caso, temos 3 opções:
Achamos o número que queríamos? Nice! Retornamos o índice dele.
O número é maior do que o que queremos? Procuramos à esquerda!
O número é menor do que o que queremos? Procuramos à direita!
A chave desse algoritmo é que o array está ordenado, ou seja, nós sabemos para que lado precisamos ir quando queremos encontrar valores menores ou maiores, ou seja, a cada operação, o conjunto de elementos em que o número que queremos achar está diminui pela metade. O (log N). Vamos ver isso em código agora:
from typing import List
def binary_search(arr: List[int], target: int) -> int:
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
if arr[mid] > target:
right = mid - 1
else:
left = mid + 1
return -1Array de Booleans Ordenado
Dado um array ordenado de booleans, retorne o índice do primeiro valor verdadeiro. Por exemplo:
[False, False, False, True, True, True]
Output: 3
[False, False, True, True, True]
Output: 2Modificando um pouco o código da busca binária mais cedo, criando uma variável para armazenar o índice do primeiro boolean no array, a função fica da seguinte forma:
from typing import List
def find_boundary(arr: List[bool]) -> int:
left, right = 0, len(arr) - 1
boundary_index = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] == True:
boundary_index = mid
right = mid - 1
else:
left = mid + 1
return boundary_indexBinary Search e Função Monótona
Um conceito interessante é que nós podemos utilizar binary search sempre que pudermos reduzir o conjunto de elementos em que nosso valor possa estar através de uma decisão binária, isso pode parecer um pouco abstrato, vamos tentar entender isso melhor. Primeiro, vamos entender o que é uma função monótona.
Uma função monótona é uma função que ou não é crescente, ou não é decrescente. Ou seja, dado x1 e x2, onde x1 > x2, os resultados devem ser f(x1) ≥ f(x2).
Um array ordenado é uma função monótona pois o valor permanece ou o mesmo ou é maior em comparação com os anteriores à medida que o índice aumenta.
Um array ordenado de booleans também é uma função monótona, pois nós podemos visualizar com uma sequência de 0s e 1s: [000111].
Binary Search Template
A condição para aplicarmos uma binary search em um array é acharmos uma função monótona que retorne ou verdadeiro ou falso, então o problema se torna achar o primeiro valor verdadeiro num array, que acabamos de resolver!
Vamos chamar essa função feasible:
def binary_search(arr: List[int], target: int) -> int:
left, right = 0, len(arr) - 1
first_true_index = -1
while left <= right:
mid = (left + right) // 2
if feasible(mid):
first_true_index = mid
right = mid - 1
else:
left = mid + 1
return first_true_indexAgora, toda questão que envolva uma binary search torna-se apenas identificar a função feasible e mecanicamente aplicar o template. Uma maravilha, não?
No problema "Primeiro Elemento Verdadeiro", a função feasible era apenas if arr[mid] == True. Achar essa função pode ser um tanto que mais complicado em outros problemas, mas nada que a prática não possa resolver.
Array Implicitamente Ordenado
Um array de números inteiros ordenado foi rotacionado em um índice não conhecido. Por exemplo, [10, 20, 30, 40, 50, 60] foi rotacionado no índice 2 e se tornou [40, 50, 60, 10, 20, 30]. Encontre o índice do menor elemento nesse array.
Input: [30, 40, 50, 10, 20]
Output: 3
Input: [3, 5, 7, 11, 13, 17, 19, 2]
Output: 7Você pode estar pensando "Esse array não está ordenado, não tem como usar binary search!", mas há uma ordem ímplicita nesse array. Veja bem, lembre-se do nosso template de binary search que apresentei pouco tempo atrás, só precisamos encontrar a função feasible. Para esse problema, tem três coisas que é importante notar:
O último elemento do array faz parte dos elementos que foram rotacionados
Se um valor x for menor ou igual ao último elemento do array, ele faz parte dos elementos que foram rotacionados
O menor valor do array faz parte dos elementos rotacionados
Com essas 3 informações, podemos definir que nossa função feasible será checar se o elemento encontrado é menor ou igual ao último elemento do array. Dessa forma, na visão da nossa função feasible, o array vai de [40, 50, 60, 10, 20, 30] para [False, False, False, True, True, True], e tudo se torna uma mera questão de achar o primeiro valor verdadeiro do array, pois é um array ordenado de forma ímplicita!
Vamos aplicar isso em código agora:
from typing import List
def find_min_rotated(arr: List[int]) -> int:
left, right = 0, len(arr) - 1
boundary_index = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] <= arr[-1]:
boundary_index = mid
right = mid - 1
else:
left = mid + 1
return boundary_indexfonte: AlgoMonster, módulo sobre Binary Search.
keywords: implicitamente ou explicitamente ordenado, decisão binária, função feasible.
Last updated