ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Знатоки покажите на Инете где почитать
18 сообщений из 18, страница 1 из 1
Знатоки покажите на Инете где почитать
    #34915428
Фотография SergLet
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SergLet
Участник
про описание алгоритма двоичного (бинарного) поиска ? Чего то не могу ничего внятного найти!
...
Рейтинг: 0 / 0
03.11.2007, 20:46
| Ответить | Цитировать | Написать  
Знатоки покажите на Инете где почитать
    #34915430
Фотография grexhide
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
grexhide
Участник
про описание алгоритма двоичного (бинарного) поиска ?
...
Рейтинг: 0 / 0
03.11.2007, 20:50
| Ответить | Цитировать | Написать  
Знатоки покажите на Инете где почитать
    #34916066
ErV
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ErV
Участник
SergLet wrote:

> Чего то не могу ничего внятного найти!
www.google.com, запрос "binary search"
--
We are all going to hell and I'm driving the bus
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
04.11.2007, 20:47
| Ответить | Цитировать | Написать  
Знатоки покажите на Инете где почитать
    #34916156
teras
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
teras
Гость
SergLet wrote:
> про описание алгоритма двоичного (бинарного) поиска ? Чего то не могу
> ничего внятного найти!

Захотелось поделиться. Долго не понимал алгоритм, и приходилось
постоянно нырять в литературу. Но после того, как один раз понял
принципы все оказалось просто до безобразия.

Двоичный поиск работает последовательным сужением интервала [A,B], до
тех пор, пока этот интервал не окажется пустым. Теперь самая важная
вешь: из определения интервала видно, что элемент с индексом A - это
первый элемент, который *может* оказаться искомым. А элемент с индексом
B - это последний элемент, который *может* оказаться искомым. Понимая
все это, весь алгоритм воссоздается в нужной форме самой простой логикой:

Инициализация: A указывает на первый элемент, B на последний элемент.
Поиск: Возьмем любой элемент лежащий в интервале [A,B], обозначим его C,
и сравним этот элемент с искомым значением. Очевидно, что у нас будет
три случая:
0) Равенство - тривиальный случай.
1) Если искомое значение меньше элемента C, то, очевидно, что нужный нам
элемент находится между A и C. Причем, про C мы уже знаем, что он точно
не является искомым, то есть - верхней границей будет элемент,
предшествующий C. Сужаем интервал до состояния [A,C-1].
2) Искомое значение больше C. Очевидно, что искомый элемент находится
между C и B, причем C так-же не является искомым. Значит, сужаем
интервал до состояния [C+1,B].

Элемент C можно выбирать по разному (например, в некоторых задачах
быстрее работает золотое сечение), но из общих соображений быстрее
разбивать интервал каждый раз пополам.

И вообще - варианты поиска очевидным образом вытекают из определения
интервала. Скажем, исключение отдельного случая равенства (0), чтобы
оставить одно сравнение, достигается изменением случая (2) - при этом
искомое значение больше либо равно C. А значит, элемент C *может* быть
искомым значением - сужаем до интервала [C,B].

Если последовательность содержит не уникальные значения, что мы, деля
интервал в произвольной точке, можем попадать не на границу
подпоследовательности. Приведенный алгоритм с сохранением случая
равенства, будет находить любой элемент подпоследовательности, при
исключении равенства, будет находить первый элемент
подпоследовательности. Тривиально изменяя обработку результатов
сравнения, мы можем находить последний элемент подпоследовательности.

Иногда удобны другие определения интервала. Например, интервал [A,B),
такой, что A - первый элемент, который может оказаться искомым, а B -
элемент который точно не является искомым. Тогда, из рассуждений
подобных приведенным строится обработка результатов сравнения.

Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
04.11.2007, 23:15
| Ответить | Цитировать | Написать  
Знатоки покажите на Инете где почитать
    #34916437
Фотография SergLet
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SergLet
Участник
ErV
SergLet wrote:

> Чего то не могу ничего внятного найти!
www.google.com, запрос "binary search"
--
We are all going to hell and I'm driving the bus
Posted via ActualForum NNTP Server 1.4 умный очень! Мне вообще так кажется что послать на гугль это как плюнуть в морду или послать нах ... да?
...
Рейтинг: 0 / 0
05.11.2007, 11:31
| Ответить | Цитировать | Написать  
Знатоки покажите на Инете где почитать
    #34916441
Фотография SergLet
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SergLet
Участник
Тарас молодец! Спасибо! Возми с полки пирожок!!!!
...
Рейтинг: 0 / 0
05.11.2007, 11:34
| Ответить | Цитировать | Написать  
Знатоки покажите на Инете где почитать
    #34916501
ErV
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ErV
Участник
SergLet wrote:

> умный очень! Мне вообще так кажется что послать на гугль это как
> плюнуть в морду или послать нах ... да?
Чувак, ты для начала-то советом воспользуйся, а потом ругайся, а?
Берешь гугл, вводишь "в кавычках" слова binary search и первым
пунктом получаешь описание гребаного алгоритма. Ещё есть гребаная
книга "жемчужины программирования", где этот алгоритм разжеван.
Писать каждому диссертации мне влом, так что пользуйся чем дают.

--
We are all going to hell and I'm driving the bus
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
05.11.2007, 12:21
| Ответить | Цитировать | Написать  
Знатоки покажите на Инете где почитать
    #34916727
teras
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
teras
Гость
SergLet wrote:
> Тарас молодец! Спасибо! Возми с полки пирожок!!!!

А ты невнимателен... И, кстати, между посыланием в google и в другие
места есть больша-а-ая разница.
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
05.11.2007, 15:12
| Ответить | Цитировать | Написать  
Знатоки покажите на Инете где почитать
    #34916736
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
SergLetумный очень! Мне вообще так кажется что послать на гугль это как плюнуть в морду или послать нах ... да?
Думаю, если ты воспримешь этот совет именно так и выполнишь его, и тебе, и нам, и программированию станет лучше.
...
Рейтинг: 0 / 0
05.11.2007, 15:17
| Ответить | Цитировать | Написать  
Знатоки покажите на Инете где почитать
    #34920586
Фотография SergLet
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SergLet
Участник
ErV
SergLet wrote:

> умный очень! Мне вообще так кажется что послать на гугль это как
> плюнуть в морду или послать нах ... да?
Чувак, ты для начала-то советом воспользуйся, а потом ругайся, а?
Берешь гугл, вводишь "в кавычках" слова binary search и первым
пунктом получаешь описание гребаного алгоритма. Ещё есть гребаная
книга "жемчужины программирования", где этот алгоритм разжеван.
Писать каждому диссертации мне влом, так что пользуйся чем дают.

--
We are all going to hell and I'm driving the bus
Posted via ActualForum NNTP Server 1.4 Вот дорогой твоя последняя фраза на ингилше наверное и выражает твой внутренний мир. Чувак - а, послушай ка меня! Я так понимаю форумы созданы для того что бы на них задавали вопросы, а те кто что то может ответить отвечали! А, ты чувак сидишь там за компом наверное и думаешь себе какой я умный, какой я крутой и офигителный прогаммист! А, ну ка посмотрю как я че там на форуме ламеры пишут, ну и снизойду до кого нибудь из них - и пошлю его на гугль и еще скажу что я такой умный и диссертации для ламеров писать не буду!!! Я правильно понял тебя Чувак? Или я что то упустил. Гугль вешь хорошая - но живое общение в среде своих единомышленников не заменит не один гугль! Если бы ты просто кинул эту ссылку то поверь мне ты бы не переломался и мир бы не рухнул! Нет надо еще раз показать кому нибудь как я крут - круче только яйца!!! Так что засунь себе свою крутость в одно место Чувак и не лезь на форумы по програмированию до тех пор пока не изменишь свое отношение к окружающим! Я ясно обьяснил Чувак?
Модератор:
забанен на двое суток
...
Рейтинг: 0 / 0
07.11.2007, 05:03
| Ответить | Цитировать | Написать  
Знатоки покажите на Инете где почитать
    #34920588
Фотография SergLet
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SergLet
Участник
softwarer SergLetумный очень! Мне вообще так кажется что послать на гугль это как плюнуть в морду или послать нах ... да?
Думаю, если ты воспримешь этот совет именно так и выполнишь его, и тебе, и нам, и программированию станет лучше. что мне тебе сказать - софтварер! Пошел ты .... знаешь куда или тебе показать направление! Я думаю тебе тоже пора валить туда где ты себе равных найдешь, а не проявлять свой опупенный интелект на ламерских форумах коими ты их считаешь! Я ясно изьясняюсь!!!
...
Рейтинг: 0 / 0
07.11.2007, 05:06
| Ответить | Цитировать | Написать  
Знатоки покажите на Инете где почитать
    #34920589
Фотография SergLet
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SergLet
Участник
teras
SergLet wrote:
> Тарас молодец! Спасибо! Возми с полки пирожок!!!!

А ты невнимателен... И, кстати, между посыланием в google и в другие
места есть больша-а-ая разница.
Posted via ActualForum NNTP Server 1.4 мне начинает казаться что это синонимы! А, гугль уже превратился в какуюто плеть для нерадивых! Бедный Сережа Брин он так стрался ...
...
Рейтинг: 0 / 0
07.11.2007, 05:07
| Ответить | Цитировать | Написать  
Знатоки покажите на Инете где почитать
    #34929592
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tchingizПривилегированный пользователь
Участник
Модератор:
разбанен
...
Рейтинг: 0 / 0
09.11.2007, 23:33
| Ответить | Цитировать | Написать  
Знатоки покажите на Инете где почитать
    #34929861
ErV
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ErV
Участник
SergLet wrote:

> Вот дорогой твоя последняя фраза на ингилше наверное и выражает твой
> внутренний мир.
Читай:
http://www.google.com/help/operators.html
http://www.ln.ua/~openxs/articles/smart-questions-ru.html

> Чувак - а, послушай ка меня!
Влом.

> Я так понимаю форумы
> созданы для того что бы на них задавали вопросы, а те кто что то может
> ответить отвечали!
Неправильно понимаешь. Объясняю последний раз:
Если вопрос задан, отвечать на него никто не обязан, даже если может.
Никто не обязан тебе чего-то разжевывать.
Ответ тебе дадут в одном из следующих случаев:
1) проблема интересная и новая.
2) проблема интересная.
3) отвечающий испытвает удовольствие от разжевывания в сотый раз одного
и того же вопроса.
4) из жалости.

Посему, если тебе все-таки хочется получать ответы на свои вопросы, то
учись пользоваться поиском . А форумы созданы для:
1) решения проблем, на которые ответ поиком найти нельзя
2) указания новичкам продвинутых методик нахождения информации и
частоиспользуемых ссылок с ответами на частозадаваемые вопросы.

Ну и также для:
3) бессмысленной болтовни
4) ругани и холиваров.

> А, ты чувак сидишь там за компом наверное и думаешь
> себе какой я умный, какой я крутой и офигителный прогаммист!
Детский сад. Чувак, сходи к психотерапевту. Или вот сюда:
http://www.antigreen.org/bioreactor/

--
We are all going to hell and I'm driving the bus
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
10.11.2007, 13:14
| Ответить | Цитировать | Написать  
Знатоки покажите на Инете где почитать
    #34930079
belugin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
belugin
Участник


еще вот
...
Рейтинг: 0 / 0
10.11.2007, 17:09
| Ответить | Цитировать | Написать  
Знатоки покажите на Инете где почитать
    #34930538
ErV
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ErV
Участник
belugin wrote:

> еще вот
Не. Это прикольно, но не то. Там инструкций по использованию нету...
--
We are all going to hell and I'm driving the bus
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
11.11.2007, 12:26
| Ответить | Цитировать | Написать  
Знатоки покажите на Инете где почитать
    #34930543
Фотография Софтверный проктолог
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Софтверный проктолог
Участник
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
/*
 * @(#)Arrays.java	1.48 03/01/23
 *
 * Copyright 2003 Sun Microsystems, Inc. All rights reserved.
 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
    /**
     * Searches the specified array of ints for the specified value using the
     * binary search algorithm.  The array <strong>must</strong> be sorted (as
     * by the <tt>sort</tt> method, above) prior to making this call.  If it
     * is not sorted, the results are undefined.  If the array contains
     * multiple elements with the specified value, there is no guarantee which
     * one will be found.
     *
     * @param a the array to be searched.
     * @param key the value to be searched for.
     * @return index of the search key, if it is contained in the list;
     *	       otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
     *	       <i>insertion point</i> is defined as the point at which the
     *	       key would be inserted into the list: the index of the first
     *	       element greater than the key, or <tt>list.size()</tt>, if all
     *	       elements in the list are less than the specified key.  Note
     *	       that this guarantees that the return value will be >= 0 if
     *	       and only if the key is found.
     * @see #sort(int[])
     */
     public   static   int  binarySearch( int [] a,  int  key) {
	 int  low =  0 ;
	 int  high = a.length- 1 ;

	 while  (low <= high) {
	     int  mid = (low + high) >>  1 ;
	     int  midVal = a[mid];

	     if  (midVal < key)
		low = mid +  1 ;
	     else   if  (midVal > key)
		high = mid -  1 ;
	     else 
		 return  mid; // key found
	}
	 return  -(low +  1 );  // key not found.
    }
...
Рейтинг: 0 / 0
11.11.2007, 12:28
| Ответить | Цитировать | Написать  
Знатоки покажите на Инете где почитать
    #34931186
Фотография Gluk (Kazan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gluk (Kazan)
Участник
из [зале]жалости ?
...
Рейтинг: 0 / 0
12.11.2007, 08:17
| Ответить | Цитировать | Написать  
18 сообщений из 18, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Знатоки покажите на Инете где почитать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=34920586&tid=1345717]:
 0ms
get settings:
 6ms
get forum list:
 9ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 186ms
get topic data:
 11ms
get forum data:
 2ms
get page messages:
 55ms
get tp. blocked users:
 1ms
others: 200ms
total:  474ms
созд. / загр.: 474ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]