Бинарный поиск. (Паскаль) - Компьютерный форум OSzone.net

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)

- Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)

- - Бинарный поиск. (Паскаль) (http://forum.oszone.net/showthread.php?t=107998)

Бинарный поиск. (Паскаль)

Мне нужно найти эллемент в массиве, использую бинарый поиск. Я отсортировал массив, убрал все повторяющиеся эллементы.
Но почему то поис работает не правельно, особенно условие выхода из цикла какойто не правельное... иногда выводит не правельный индекс элемента, иногда не выходит из цикла если число попало ровно на середину... потаму что потом идёт увеличение на 1
можете пожалуйсто помоч.

Код:

  repeat

    write('введите позитивное число, которое программа попробует найти в массиве - ');

    readln(srch);

  until(srch>0);

  Lb:=0;

  Ub:=n;

  repeat

    mid:=(Lb + Ub) div 2;

    if (srch < mass[mid]) then

    begin

      Ub := mid - 1;

    end

    else if (srch > mass[mid]) then

    begin

      Lb := mid + 1;

    end;

  until((mid=srch)or(mid=ub)or(mid=lb));

  if (mid=srch) then

  begin

    writeln('Число которое вы хотели найти',srch,'  и на ходиться на позиции ',mid);

  end;

n это констанка которая равна 20.
размер массива [1..n]

S1stem, слово "правильно" пишется через "и". Ну и вообще, русский язык надо любить больше, чем паскаль :)

Цитата:

Цитата S1stem

until((mid=srch)or(mid=ub)or(mid=lb));
if (mid=srch) then »

mid - это индекс в массиве, вы ищите совпадение значений, поэтому данный кусок надо переписать так:

Код:

  until((mass[mid]=srch)or(mid=ub)or(mid=lb));

  if (mass[mid]=srch) then

К тому же, так как индексация массива начинается с 1, то и Lb надо сначала присваивать значение равное 1.

Остальное вроде правильно.

Может не в тему языка, но на С++ это выглядит так, если можешь перевести на Pascal или форумчане переведут... То вот...

Код:

//Бинарный поиск

#include <iostream>

using std::cout;

using std::cin;

using std::endl;



#include <iomanip>

using std::setw;



int binarySearch(const int[], int, int, int, int);

void printHeader(int);

void printRow(const int[], int, int, int, int);



int main()

{

   int const arraySize = 15; 

   int z, 

       a[arraySize],

       key,

       result;



   for(int i = 0; i < arraySize; i++)

      a[i] = 2 * i;



   cout<<"ENTER NUMBER IN DIAPAZON 0 AND 28: ";

   cin>>key;

   

   while(key != -1){

       printHeader(arraySize);

       result = binarySearch(a, key, 0, arraySize - 1, arraySize);

       if(result != -1)

          cout<<'\n'<<key<<" FOUND THE ELEMENT OF MASSIVA "<<result<<endl;

       else

          cout<<'\n'<<key<<" NO FOUND "<<endl;

      

      cout<<"ENTER NUMBER IN DIAPAZON 0 AND 28: ";

      cin>>key;

    }

   return 0;

}



// Функция бинарного поиска

int binarySearch(const int b[], int searchKey, int low, int high, int size)

{

   int midlle;

   

   while(low <= high){

       midlle = (low + high) / 2;

       printRow(b, low, midlle, high, size);

       if(searchKey == b[midlle])

           return midlle;

       else if(searchKey < b[midlle])

           high = midlle - 1;            // определение нижнего конца массива

       else

           low = midlle + 1;             // определение верхнего конца массива

     }

   return -1;

}



// Первоначальнный массив с рассположенными элементами

void printHeader(int size)

{

   int i;



   cout<<"\nINDEKS:\n";

   for(i = 0; i < size; i++)

      cout<<setw(3)<<i<<' ';

  

   cout<<'\n';

   

   for(i = 1;  i<= 4 * size; i++)

      cout<<'-';

   

   cout<<endl;

}



// Функции графического представления бинарного поиска 

void printRow(const int b[], int low, int mid, int high, int size)

{

   for(int i = 0; i < size; i++)

      if(i < low || i > high)

         cout<<"    ";

      else if(i == mid)                // отметить среднее значение

         cout<<setw(3)<<b[i]<<'*';

     else

         cout<<setw(3)<<b[i]<<' ';

        

   cout<<endl;

}

ivank - больше спасибо =)))) всё ок теперь работает.