Corretude por invariante - Busca binária

[@fabiocaravieri5121]

suas aulas de complexidade de algoritmos é muito boa. Você tem o material em slides ou pdf para estudo?

Tem no site dela.

Posso mandar o link aqui, não sei se o youtube vai permiitir: professor.ufabc.edu.br/~carla.negri/cursos/materiais/Livro-Analise.de.Algoritmos.pdf

[@henriquecoala2723]

muito bom!

[@DanielDlc.]

Muito bom

[@brenobcsilva]

👏👏👏👏👏👏👏👏

[@filipimacielrodriguesjardi6833]

Eu não entendi quando foi feito o passo: (x+y)/2 - 1 > 2x/2 - 1, o que houve com o y? Qual manipulação foi usada?

[@gabrielmartinssilva7613]

Vim nos comentários justamente pra ver se alguém tinha entendido, kkk

[@vitorveras138]

Acredito que tenha haver com o fato de x ≤ y, daí substituindo o valor de y por x vc consegue chegar a esse resultado, tanto pto x como y. Acredito q seja isso kk

[@CarlaNegriLintzmayer]

Oi gente! Demorei mas vi o comentário 😳 Mas é o que o Vitor falou, usei o fato de y > x.

[@parkysa1814]

@@CarlaNegriLintzmayer eu ainda não entendi, pode me explicar com mais detalhes?

[@henriquecoala2723]

#include int bb(int array[], int n, int k) { int esq = 0; int dir = n - 1; while(esq < dir) { int meio = (esq + dir)/2; if(k>array[meio]) { esq = meio + 1; } else { dir = meio; } } if(array[esq] == k) { return esq; } else { return -1; } } void ordenar1(int tam, int array[],int i, int j) { if(i < tam) { if(j < tam) { if(array[i] > array[j]) { int aux = array[i]; array[i] = array[j]; array [j] = aux; } ordenar1(tam,array,i,j+1); } else { ordenar1(tam,array,i+1,i+2); } } } int main() { int chave; int n; int array[1000]; printf("Digite o valor da chave: "); scanf("%d", &chave); printf("Digite o tamanho do array: "); scanf("%d", &n); printf("Preencha o array: "); for(int i = 0 ; i< n ; i++) { scanf("%d", &array[i]); } ordenar1(n, array, 0, 0); printf(" ################################################################# "); printf("Array ordenado: "); for(int i = 0 ; i< n ; i++) { printf("valor :%d - pos: %d ", array[i], i); } int retorno = bb(array, n, chave); printf(" A posicao da chave eh: "); printf("%d ", retorno); }