Выполнение основного задания по программированию для класса абстракции данных и ADT. Это отсортированный связанный список * типа «вложенных классов», на которые ссылается среда указателей. Алгоритм бинарного поиска представлен нам в виде псевдокода ниже.
**ALGORITHM** *BinarySearch*(A[0...n-1], n, k)* //appropriate for get & remove //pre: A is sorted in ascending order, n is the number of items in the array // k is the item being searched for //post: if the search is successful the index of the match is returned( 1-based) //if the search is unsuccessful, -1 is returned f <-- 0 // 0-based indices used in this method I <-- n-1 /* personal note. I think its an I, the pdf could be an l though */ /* personal note - I think the above is an I, pdf font could be an l though. --- secondly, the brackets in this pseudocode are bottom-half brackets. ---- i.e., they could be "floor" or "minimum"-based brackets of a kind */ m <-- f + [(i-f)/2] // floor-brackets while f <= I do { if (K = a[m]) // not-floor brackets, just subscript return (m + 1) else if ( K < A[m] ) // not-floor brackets, just subscript I <-- m-1 else f <-- m+1 m <-- f + [(I-f)/2] /* floor-based brackets */ return -1
вторая половина алгоритма
**ALGORITHM** *BinarySearch*(A[0...n-1], n, k) // appropriate for Add function //pre: A is sorted in ascending order, n is hte number of items in the array // K is the term being searched for //post: if successful, index is returned (1-based) // if the search is unsuccessful, the index of the current location is returned //what if n = 0? (that is, the first item is being added to the list) f <-- 0 //0-based indices used in this method I <-- n-1 ** m <-- f + [(I-f)/2] /* floor-based square brackets */ while (f <= I) do // int comp = (*compare)(K, A[m])[function ptr] if(K = A[m] ) // not-floor brackets, just subscript // comp == 0, duplicate found, add here, adjust for 1 return (m + 1) else if( K < A[m] ) // comp < 0 I <-- m-1 else f <-- m+1 m <-- f + [(I-f)/2] // these are floor-brackets, but what is M in all this? return m+1 //Not found, but current mid position is the location to add
Я понимаю большинство из них, но у меня возникли проблемы с переводом некоторых из его стиля записи. Я не совсем уверен, что F, I и M все время, или как они полностью применяются.
Может быть, ‘F’ — это вызов функции, применяемый для рекурсивного характера этого алгоритма?
Конечно, это общий шаблон для переменных, заменяемых реальными объектами и именами кода.
Тем не менее, я пытался искать обобщенные шаблоны алгоритмов двоичного поиска, но я, кажется, плохой при поиске подходящих примеров шаблонов определенных типов методов. Особенно на cplusplus.com, когда поиск кода дает мне этот продвинутый пример, который никоим образом даже НЕ ПОПЫТАЕТСЯ быть попыткой ввести общую концепцию того, что конкретный метод или функция вообще делает, или что он всегда делает или не делает иметь.
Итак, не могли бы вы помочь мне разобраться, что говорит этот псевдокод? Может быть, направить меня к хорошему шаблону того, каким может быть шаблон двоичного алгоритма поиска, чтобы сравнить с ним, чтобы помочь мне построить тело функции и определение?
Задача ещё не решена.
Других решений пока нет …