From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <glacs-smoke-room@m.gmane.org>
X-Injected-Via-Gmane: http://gmane.org/
To: smoke-room@lists.altlinux.org
From: Denis Kirienko <dk@altlinux.ru>
Date: Mon, 20 Aug 2007 18:38:27 +0400
Message-ID: <fac913$2pu$1@sea.gmane.org>
References: <20070820071848.GE28425@osdn.org.ua>
	<fabgh3$f8b$1@sea.gmane.org>	<679044850708200053s38259ceeo72a85bbd83e42a48@mail.gmail.com>	<fabhms$ina$1@sea.gmane.org>	<679044850708200131w20fca834oad4c5b42de00e281@mail.gmail.com>	<fabkjk$qlt$1@sea.gmane.org>
	<679044850708200716p77936decm23313342f5924d2a@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=KOI8-R
Content-Transfer-Encoding: 8bit
X-Complaints-To: usenet@sea.gmane.org
X-Gmane-NNTP-Posting-Host: 212.65.71.74
User-Agent: Thunderbird 2.0.0.6 (X11/20070804)
In-Reply-To: <679044850708200716p77936decm23313342f5924d2a@mail.gmail.com>
X-Enigmail-Version: 0.95.2
Sender: news <news@sea.gmane.org>
Subject: Re: [room] on binary search and merge-sort algos
X-BeenThere: smoke-room@lists.altlinux.org
X-Mailman-Version: 2.1.9rc1
Precedence: list
Reply-To: dk@altlinux.ru, =?koi8-r?b?y9XM2NTV0s7ZyiDPxtTP0MnL?=
	<smoke-room@lists.altlinux.org>
List-Id: =?koi8-r?b?y9XM2NTV0s7ZyiDPxtTP0MnL?= <smoke-room.lists.altlinux.org>
List-Unsubscribe: <https://lists.altlinux.org/mailman/listinfo/smoke-room>,
	<mailto:smoke-room-request@lists.altlinux.org?subject=unsubscribe>
List-Archive: <http://lists.altlinux.org/pipermail/smoke-room>
List-Post: <mailto:smoke-room@lists.altlinux.org>
List-Help: <mailto:smoke-room-request@lists.altlinux.org?subject=help>
List-Subscribe: <https://lists.altlinux.org/mailman/listinfo/smoke-room>,
	<mailto:smoke-room-request@lists.altlinux.org?subject=subscribe>
X-List-Received-Date: Mon, 20 Aug 2007 14:38:54 -0000
Archived-At: <http://lore.altlinux.org/smoke-room/fac913$2pu$1@sea.gmane.org/>
List-Archive: <http://lore.altlinux.org/smoke-room/>

Damir Shayhutdinov пишет:

>> То, что вы предлагаете - это тот же тернарный поиск, только проверка еще
>> одного условия вынесена в условие цикла.

> Тогда вы просто слишком формально относитесь к понятию "бинарный поиск".

Может быть.

> Если я правильно понимаю, то, что вы назовете бинарным поиском, будет
> _всегда_ выполняться за O(log n).

Да.

> А этот алгоритм "тернарного" поиска будет выполняться за O(log n)
> только в _худшем_ случае.

И всё равно за O(log n) в среднем...

--
Денис