programação

Algoritmo para busca binaria em uma matriz de inteiros ordenada
Gustavo Cipriano Mota Sousa
30 de Mar¸o de 2005 c Ao longo da explica¸˜o do algoritmo, os nomes escritos entre parenteses ca representam variaveis no codigo encontrado logo abaixo. Este ´ o c´digo e o da fun¸˜o bsearch helper(), localizada no arquivo matriz.c encontrado neste ca mesmo diret´rio, e ´ o respons´vel pela busca do elemento na matriz. o e a A ideia por tr´s do algoritmo e encontrar o ponto na diagonal principal a no qual o valor anterior na diagonal seja menor que (value) e o proximo valor na diagonal seja maior que (value). Dessa forma, a partir deste ponto os valores a equerda e acima do valor anterior sao menores que (value), e os valores a direita e abaixo do proximo valor sao maiores que (value). Logo sobram dois quadrantes para localizar a busca.
1. O primeiro passo do algoritmo ´ determinar o tamanho da menor die mens˜o. e armazen´-lo em (size), isso e feito para que a diagonal utia a lizada durante o algoritmo nao passe os limites da matriz.
2. Logo ap´s, testamos se a matriz possui ao menos um elemento, caso o contrario, a fun¸˜o retorna 0 ca 3. Para determinar o ponto que procuramos na diagonal principal, fazemos uma especie de busca bin´ria pela diagonal principal, come¸amos a c com um apontador para o ponto inicial (left), e para o final (right) e ent˜o calculamos o ponto central (middle). Logo apos, testamos (value) a com o elemento do meio, caso sejam iguais, encontramos o elemento, caso (value) seja menor que o elemento mediano, sabemos que (value) n˜o se encontra a direita nem abaixo do elemento mediano, e podemos a passar o elemento final (right) para o ponto imediatamente anterior ao elemento do meio na diagonal. O contr´rio ´ feito se (value) for maior a e que o elemento do meio.
1

4. Ap´s o passo anterior podemos delimitar os quadrantes que ainda preo cisam ser analisados, e para realizar essa operacao chamamos a fun¸˜o
ca