[C] przeszukiwanie binarne

Witam, jako zadanie mam zrobić program, który przeszukuje binarnie ciąg uporządkowanych elementów w poszukiwaniu jednego z nich.

Oto kod procedury, który napisałem i według mnie jest bez skazy ;) :

void szukanie(int ciag[], int liczba, int szukana)
{
 int start=0;
 int end=liczba;  //liczba jest liczbą elementów w ciągu
 int srodek;
     
 do    
 {
    
 srodek=(start+end)/2;
     if (ciag[srodek]==szukana) 
     {
     printf ("%d", srodek+1);
     break;
     getchar();
     }
        else
        {
            if(szukana<ciag[srodek])
            {
            start=0;
            end=srodek-1;
            }
                         else
                         {
                         start=srodek+1;
                         end=liczba;
                         }
        }                        
     if (start>end) printf("-1\n");
     }    
while (start<end);
} 

Niestety program nie działa prawidłowo. Nie wiem czy wykorzystana przez mnie pętla do...while jest odpowiednia? Gdzie leży błąd?

Dodam, że zamiana while (start<end); --> while (start=<end); rozwiązuje problem dla ciągu (1,2,3) gdy szukam {1}. Niestety nie działa nadal dla przeszukiwania ciągu (1,2,3,4) w poszukiwaniu {2}.

Zamiast korzystać z gotowców, które na bank można znaleźć, wolałbym wskazanie błędu w moim kodzie/rozumowaniu.

Pozdrawiam
Bart

#include <stdio.h>

void szukanie(int ciag[], int liczba, int szukana)
{
	int start=0;
	int end=liczba-1;  //indeks ostatniego elementu tablicy
	int srodek;
     
	do{
		srodek=(start+end)/2;
		if (ciag[srodek]==szukana){
			printf ("znaleziono na miejscu: %d\n", srodek+1);
     			break;
			getchar();
		}
		else{
			if(szukana<ciag[srodek])
				end=srodek-1;
			else
				start=srodek+1;
        	}                       
		if (start>end) printf("nie znaleziono\n");
     }while (start<=end);
} 

int main(){
	int tab[]={1,3,5,6,9,10};
	int a,i;
	int b=sizeof(tab)/sizeof(int);
	printf("%d\n",b);
	for(i=0; i<b; i++)
		printf("%-3d",tab[i]);
	printf("\nWprowadz szukana liczbe\n");
	scanf("%d", &a);
	szukanie(tab,sizeof(tab)/sizeof(int),a);
	return 0;
}

iksarp napisał(a)

zamiast

int end = liczba;

daj

int end=liczba-1

Dzięki :). Teraz to jest oczywiste ;). Przypuszczałem, że gdzieś tu jest problem(o jedna liczba za dużo), ale nie wiedziałem gdzie dokładnie coś zmienić.
Zmieniłem jeszcze " if (start>end) printf("-1\n");" na "if (start>=end) printf("-1\n");" i program działa bez zarzutu.

Teraz tylko muszę to napisać w wersji rekurencyjnej... więc pewnie się jeszcze odezwę.

Pozdrawiam

Zedytowalem stary post, załozmy ze zaspany bylem i strzeliłem wielka gafe - dla danych ze starego postu tez nie bedzie dzialal poprawnie(np. sprobuj znalezc 3 w 1,2,3,4). Wklejony teraz przeze mnie kod jest poprawny, zobacz roznice i pomysl z czego moga wynikac

iksarp napisał(a)

Zedytowalem stary post, załozmy ze zaspany bylem i strzeliłem wielka gafe - dla danych ze starego postu tez nie bedzie dzialal poprawnie(np. sprobuj znalezc 3 w 1,2,3,4). Wklejony teraz przeze mnie kod jest poprawny, zobacz roznice i pomysl z czego moga wynikac

Czyżby chodziło o instrukcje po obu "else"? Skasowałem po jednej linijce w każdym i teraz wyszkuje 3 w ciagu 1,2,3,4. Jakieś jeszcze kłopotliwe sytuacje?

Główny kod programu mam nieco inaczej (normalniej?). Nie wykorzystuję sizeof'ów (swoją drogą mógłbyś mi nieco wytłumaczyć co robi sizeof(int)?, oraz nieco nakreślić działanie tych linijek:

int b=sizeof(tab)/sizeof(int);  //zwłaszcza tej...
       printf("%d\n",b);
for(i=0; i<b; i++)
       printf("%-3d",tab[i]);    //...i tej

w zmiennej b jest przechowywana ilosc elementow tablicy, a taka pomocnicza zmienna, poniewaz zmienialem "recznie" tablice w kodzie programu.

a co do printfow i flag, dobrze wytlumaczone pod tym adresem :
http://www.fizyka.umk.pl/~norbert/C/printf_i_scanf.htm

btw. wiesz juz czemu skasowalem wspomniane przez ciebie instrukcje po else?

Dzięki za odpowiedzi :)

Myślę, że wiem dlaczego te instrukcje trzeba skasować (mogłyby one przywrócić do stanu początkowego coś, co powinno zostać zmienione, racja?).

tak, a dokladniej zasieg przeszukiwania w tablicy