Вобщем нужно реализовать бинарный поиск квадратной матрице А[n][n] по диагоналям, параллельным побочной (т.е. диагоналями здесь будут эл-ты A[0][0], A[n-1][n-1], побочная диагональ и все параллельные ей)
Алгоритм поиска вот такой:
| Код |
char string[]="0245789AAABDFHJKLXYZ"; // sorted ASCIIZ string
char symbol='J'; // symbol to find
unsigned int left,right; // bounds of the area where we search
unsigned int middle; // center of the area where we search
unsigned int length=sizeof(string)/sizeof(char); // string length
void main(void)
{
printf("String: %s\n",string);
left=0;
right=length-1;
while (left<right)
{
middle=(left+right)/2;
if (string[middle]<symbol) left=middle+1; else right=middle;
}
}
|
по-подробней он описан http://forum.vingrad.ru/forum/topic-37776.html#st_15_view_0.
С другим алгоритмом бинарного поиска я уже разобрался и реализовал, 
А вот с приведённым выше - нифига не получается  .
Короче ближе к делу - Я ни как немогу найти у себя в коде ошибку из-за которой поиск не работает!
Вот ф-ция, которая работает(упрощённый алгоритм бинарного поиска):
| Код |
template <class Type> bool bin_search1(Type **a, Type *b, int n2, int n, Type x){
int i, j, k, Li, Ri, Lj, Rj, Mi, Mj;
bool found ,res = false;
for(i=0;i<n;i++){ //поиск в первых n - диагоналях
Li = i;
Lj = 0;
Ri = 0;
Rj = i;
found = false;
while(Lj<=Rj && !found){
Mi = (Li + Ri)/2;
Mj = (Lj + Rj+1)/2;
if(a[Mi][Mj] == x){
found = true;
b[i] = Mj+1;
res = true;
}
else
if(a[Mi][Mj]<x){
Li = Mi-1;
Lj = Mj+1;
}
else{
Ri = Mi+1;
Rj = Mj-1;
}
}
/*for(i=1;i<n;i++){ //поиск в остальных n-1 - диагоналях
k=1;
for(j=i;j<n;j++){
a[n-k][j];
k++;
}
}*/
}
return res;
}
|
Пояснение:
Этой ф-ции передаётся двумерный массив n*n(ну или квадратная матрица), в котором(-ой) и нужно произвести поиск заданного элемента(x) по диагоналям, параллельным побочной - диагонали пронумерованы начиная с эл-та A[0][0] - диагональ №0 и заканчивая элементом A[n-1][n-1] - диагональ №2n-2. Т.е. как вы поняли, сама побочная диагональ будет иметь номер n-1.
Диагонали отсортированы по неубыванию слева на право.
Затем производится сам поиск и результаты поиска заносятся в одномерный массив b, т.е если в i-ой диагонали эл-т найден, то его позиция в диагонали заносится в b[i].
Ну а n2 - ненужный пока параметр.
Так вот, как я уже говорил, эта функция работает, и суть вопроса в том почему не работает эта функция:
| Код |
template <class Type> bool bin_search2(Type **a, Type *b, int n2, int n, Type x){
int i, j, k, Li, Ri, Lj, Rj, Mi, Mj;
bool res = false;
for(i=0;i<n;i++){ //поиск в первых n - диагоналях
Li = i;
Lj = 0;
Ri = 0;
Rj = i/*+1*/; //Вот тут "+1" не надо! )))
while(Lj<Rj){
Mi = (Li + Ri+1)/2;
Mj = (Lj + Rj)/2;
if(a[Mi][Mj]<x){
Li = Mi-1;
Lj = Mj+1;
}
else{
Ri = Mi;
Rj = Mj;
}
}
if(a[Ri][Rj] == x){
b[i] = Rj+1;
res = true;
}
}
/*for(i=1;i<n;i++){
k=1;
for(j=i;j<n;j++){
a[n-k][j];
k++;
}
}*/
return res;
}
|
Как видите, это тоже бинарный поиск, но немного модифицированный.
Кто скажет, где ошибка?
P.S. не обращайте внимание на то, что ф-ции ищут только в первых n-диагоналях, потом доделаю.
Я сам всё понял , но всё равно Большое Спасибо всем товарищам форумчанам и до скорых встреч.
|