C > 配列の中から一番近い値を探索 (double型) > v0.1

動作環境

C++ Builder XE4

背景

• C++ BuilderにてTDateTime型(double型として)で近い値の要素を取得
• 二分探索でやってみよう

情報

そもそも自前実装でなく、すでにあるのでは?

• https://cpprefjp.github.io/reference/algorithm/binary_search.html
  • 二分探索
  • 戻り値がbool型であり、インデックスは分からない

自前実装しよう。

• https://en.wikibooks.org/wiki/Algorithm_Implementation/Search/Binary_search
  • 様々な言語での実装
  • C実装を参考にした
  • ただし、こちらはint型での探索でありdouble型ではない
    • double型へは自分で検討した

実装 v0.1

C++向けであるが、Cとして実装してみた。
(組込みでも使う?)

• https://ideone.com/BFUgOE

# include <stdio.h>

int BinarySearch(double *vals, int size, double ref);

int main(void) {
	// list to be searched (sorted)
	double vals[] = { 2.718, 3.14, 6.022, 10.23 };
	int size = sizeof(vals)/sizeof(vals[0]);

    // list where each value is searched
	double chks[] = { 2.0, 3.13, 3.14, 3.15, 15.0 };
	int num = sizeof(chks)/sizeof(chks[0]);

	for(int idx=0; idx<num; idx++) {
		int pos = BinarySearch(vals, size, chks[idx]);
		if (pos >= 0) {
			printf("pos = %d, %f for %f\n", pos, vals[pos], chks[idx]);
		} else {
			printf("not found for %f\n", chks[idx]);
		}
	}
	return 0;
}

int BinarySearch(double *vals, int size, double target) {
	int start = 0;
	int end = size - 1;
	int mid;
	
	if (target < vals[start] || target > vals[end]) {
		return -1;
	}

	while (start <= end) {
		mid = (start + end) / 2;
		if (mid == (start+1) && (target >= vals[start]) && (target < vals[mid])) {
			return start;
		} else if (target < vals[mid]) {
			end = mid - 1;
		} else {
			start = mid + 1;
		}
	}
	
	if (end < start) {
		return end;
	}
	return start;
}

動作例

{ 2.718, 3.14, 6.022, 10.23 }に対して

not found for 2.000000
pos = 0, 2.718000 for 3.130000
pos = 1, 3.140000 for 3.140000
pos = 1, 3.140000 for 3.150000
not found for 15.000000

備考

それっぽいのはできた。

変数名が適当なので、実際に使う時にもう少し検討

そもそも

C++またはC++ Builderのライブラリで目的の動作となる関数がライブラリにあるのでは?

それを見つけられていない。

関連

Delphi実装で見つけたのは以下

• Searching nearest value in sorted array