Задача: реализовать поиск в строке методом деления пополам. Строка состоит из символов и вводится пользователем. Ключ для поиска - символ. Необходимо определить порядковые номера его вхождений в искомую строку.

Добавлено @ 14:28 
Общая идея такая. Разбиваем строку на отдельные символы. Создаём список в котором каждому символу присваиваем список с номерами его позиций в строке. Затем сортируем список по порядку расположения символов в таблице ASCII (напимер методом пузырька). Затем операция поиска. В этом списке сравниваем элемент в центре с ключём. Если равен, то ответ найден. Если больше продолжаем поиск в списке справа. Если меньше - слева.

Чёто я не понял, есть в Lisp способ сравнить два символа (например: а и b) кроме как на равенство? < и > не работают. 

А как насчет char> или char< ? 

 Действительно работает. Странно, сколько в книгах не рылся не видел такого предикаты. Эх, где бы найти список встроенных функций. Большое спасибо. А то я уже в Visual Lisp полез.

Что Вы называете "символом"? Если CHARACTER, то CHAR< или CHAR-LESSP, если SYMBOL, то STRING< или STRING-LESSP.
Ссылка на стандарт ANSI Common Lisp, переведенный в формат HTML: http://www.lispworks.com/documentation/HyperSpec/index.html

  Первую часть сделал: построение и сортировка ассоциированного списка. 

У кого есть замечания прошу говорить. Я пока поиск буду делать.

У (STRING (READ)) будут большие проблемы со скобками во входном потоке. Лучше написать (READ-LINE).
Вычислять на каждой итерации заново длину списка - это несколько неоптимально. Я бы использовал DOTIMES или LOOP:

Для сортировки существует встроенная функция SORT, нужно только правильно задать предикат или ключ:

А тебе надо различать регистр символов? Если нет,  то надо юзать char-greaterp вместо char>
И раз у тебя в задачу входит только бинарный поиск, то я бы сортировку и остальные вспомогательные действия возложил на уже имеющиеся возможности lisp'а.

make-char-hash делает хэш-таблицу, ключами которой являются символы (для регистронезависимости надо дополнительно указать :test 'equalp), а значениями -- позиции, в которых встречаются эти символы.
has-keys-list делает список из ключей хэш-таблицы.
Соответственно, вся подготовка к бинарному поиску сведется к созданию хэша символов, списка символов из него и его сортировке встроенной функцией sort, после чего можно непосредственно реализовывать бинарный поиск.

Уважаемый Agarwaen, прочитав Ваше "задание" и "общую идею" (сообщение №1), остаемся в полном недоумении по следующим основаниям:
Задача - "...необходимо определить порядковые номера его (знака) вхождений в искомую строку"
Общая идея - "...каждому символу (то есть знаку) присваиваем список с номерами его позиций в строке. Затем..."
Если уже есть в наличии список номеров позиций, тогда зачем все действия после слова "затем"? Однако зачем таковой список для каждого знака, если заранее известен искомый знак?

 Это же учебная задача. Ясно что в реальной жизни никто такой геморой устраивать ради поиска в строке не будет. Реальное применение бинарного поиска мне видится только в поиске по таблице-справочнику, в которой ключи уже отсортированы.

Это сообщение отредактировал(а) Agarwaen - 5.1.2007, 21:34

Такая учебная задача успешно может привить только отвращение к учению. Извините, а Вы часом не преподаватель подобных задач?
Опрос Интернета по поводу "бинарного (двоичного) поиска" позволил составить отчетливое представление о том, что сей алгоритм эффективен при поиске (1) определенного, (2) присутствующего в одном экземпляре элемента в (3) упорядоченном массиве подобных элементов. Согласитесь, что произвольная строка, в которой может присутствовать таких элементов от нуля до числа знаков в строке весьма далека от упорядоченного массива.

 Да я всё это понимаю, и сам уже на пределе. Такую задачу мне пришлось сделать на 3 языках: на С++, Prolog и Lisp. Просто наш препод первый семестр преродаёт этот предмет. Я думаю он эти задания придумал за пару часов чтоб просто выдать, а вспомнить уже на защите.  

Я конечно приношу Вам свои извинения, а преподов таких - в (gc)

 Сделал функцию поиска, но она выдаёт только одну позицию символа.

 Чтобы выдавала все позиции нужно наверно или изменить функцию, или переделать список. У кого есть замечания? Предыдущие были очень полезны, только времени переделывать уже нет особо.

Это сообщение отредактировал(а) Agarwaen - 6.1.2007, 17:18

 Хм, я посмотрел вариант с хэш-таблицей очень хорош. Вот только нужно наверно саму хеш-таблицу переделать в список и его отсортировать, в нём же искать. Вопрос: как это сделать?

После сортировки списка пробежаться по нему и объединить последовательные записи с одинаковым ключом:
((a . 1) (b. 2) (b . 4) (c . 3)) => ((a . (1)) (b . (2 4)) (c . (3)))
Пара замечаний по стилю.
- Нехорошо присваивать значения неописанным глобальным переменным (типа R в BISEARCH и L в DEMO). В Вашем случае лучше воспользоваться LET.
- COND нужен специально для разбора нескольких случаев:

В READSTRING проверку (= INDEX 1) можно заменить проверкой (= INDEX 0). Тогда функция будет работать со строками нулевой длины и можно будет убрать копию SETQ.

Вот вариант с хеш-таблицей всё работает как надо. Если есть замечания, пишите.

Забыл сразу написать: поиск элемента с заданным номером в списке - операция медленная. Лучше было перед поиском (или перед сортировкой) перевести список в вектор.

Ну тебе надо только получить список изо всех ключей хэш-таблицы. Для этого maphash придуман.