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 12:00:25 +0400
Message-ID: <fabhms$ina$1@sea.gmane.org>
References: <20070820071848.GE28425@osdn.org.ua> <fabgh3$f8b$1@sea.gmane.org>
	<679044850708200053s38259ceeo72a85bbd83e42a48@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: <679044850708200053s38259ceeo72a85bbd83e42a48@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 08:00:41 -0000
Archived-At: <http://lore.altlinux.org/smoke-room/fabhms$ina$1@sea.gmane.org/>
List-Archive: <http://lore.altlinux.org/smoke-room/>

Damir Shayhutdinov пишет:
>> А я бы у школьника на зачете такой бинарный бы поиск не принял.
>> Поскольку он не бинарный, а тернарный - внутри идет ветвление на три
>> возможных случая.
> Если уж придираться - то по полной. Там на самом деле четыре возможных
> случая, включая проверку в while (low <= high).

А вот этого я уже не понимаю. Условие-то в цикле должно быть по-любому,
от него никуда не денешься.

Суть бинарного поиска в том, что массив на каждом шаге делится на две
части, между которыми осуществляется выбор. В том алгоритме, который
приведён по ссылке массив делится на три части.

--
Денис