binary-search.js

*linear:
	- somente 1 dimensao
	- lista finita e sequencial de items

A escolha do metodo a ser utilizado depende de:
	- quantidade de dados envolvidos
	- volume de operacoes de inclusao/exclusao

Algoritmos relacionados à memória primária
	Busca linear/sequencial
	- esforço: N
	- faz a busca pelo valor desejado ate que o encontre, andando uma posicao de um array por vez, por exemplo
	- ideal quando nao se tem informacoes da estrutura que sera feita a pesquisa
	- caso o elemento esteja entre os ultimos, o programa pode ser lento

	Busca binária
	- esforço: log N
	- utilizado quando temos uma sequencia ordenada de dados
	- dividi-se a sequencia em blocos sucessivamente, ate que o elemento seja encontrado

var array = [1,2,3,4,5,6,7,8,9];
function binarySearch( value, array ) {
	// extrai o elemento da metade do array
	var middleElement = array[Math.round(array.length/2)-1];
	
	// se o elemento da metade for igual ao valor procurado
	if ( value === middleElement ) {
		console.timeEnd('binarySearch');
		return true;
	// quando nao restarem mais elementos no array
	} else if ( array.length === 1 ) {
		console.timeEnd('binarySearch');
		return false;
	// enquanto nao encontrar, continua procurando
	} else {
		// se o valor procurado for menor que o elemento da metade, faz a busca pelos elementos da esquerda
		if ( value < middleElement ) {
			var leftArray = array.slice(0, array.length/2);
			return binarySearch( value, leftArray );
		// se o valor procurado for maior, faz a busca pelos elementos da direita
		} else {
			var rightArray = array.slice(array.length/2, array.length);
			return binarySearch( value, rightArray );
		}
	}
}



console.time('binarySearch');
binarySearch(5, array);