バイナリサーチの間違い

バイナリサーチでは最初の添え字がfirstになり、最後の添え字、また要素数がlastになるという事を聞きました。
しかし、このコードではlastはlength-1になっています。
挿入するたびにlengthを増やしているから、もちろんlengthは要素数となり、
last=lengthにしなくてはいけないのではと思いました。
ご指摘のほど、よろしくお願いします。

コード
void Sortedlist::InsertItem(ItemType item) {
	bool moreToSearch;
	int location = 0;

	moreToSearch = (location < length);
	while (moreToSearch) {
		switch (item.ComparedTo(info[location])) {
		case LESS:
			moreToSearch = false;
			break;
		case GREATER:
			location++;
			moreToSearch = (location < length);
			break;
		case EQUAL:
			break;
		}
	}
	for (int index = length; index > location; index--)
		info[index] = info[index - 1];
	info[location] = item;
	length++;
}

コード
void Sortedlist::RetrieveItem(ItemType &item, bool &found) {
	int midPoint;
	int first = 0;
	int last = length - 1;

	bool moreToSearch = first <= last;
	found = false;
	while (moreToSearch && !found) {
		midPoint = (first + last) / 2;
		switch (item.ComparedTo(info[midPoint])) {
		case LESS:
			last = midPoint - 1;
			moreToSearch = first <= last;
			break;
		case GREATER:
			first = midPoint + 1;
			moreToSearch = first <= last;
			break;

		case EQUAL:
			found = true;
			item = info[midPoint];
			break;
		}
	}
}

行動規範の内容に同意します

回答2件

ベストアンサー

こんにちは。

reotantanさんのタイプミスと思いますが、混乱を避けるため、まず訂正です。恐らく、下記のように書こうとされたのですよね？

バイナリサーチでは最初の添え字がfirstになり、最後の添え字＋１、また要素数がlastになるという事を聞きました。

であれば、この件、この質問への下記私の回答ですね。

バイナリー・サーチでは、minは「検索対象の先頭データの位置」で、maxは「検索対象の最終データの位置＋１」で管理します。

ごめんなさい。私の書き方が悪かったです。正しくは下記のように書くべきでした。

maxは「検索対象の最終データの位置＋１」で管理することができます。

バイナリーサーチでは中点を求めます。その計算した中点が端数だった時、切り上げ、切り下げのどちらで処理しても、アルゴリズム上問題ありません。ということは、(first+last)/2の際lastの値が1つ大きいかそうでないかは、結果に影響しません。・・・①
先の回答を書いた時、この点を見落としていました。