[c言語]バイナリーサーチ(二分探索)のサンプルコード

バイナリーサーチ(二分探索)

まずは、下記のように、ソート・ユニークされた配列を対象にします。

int arr[MAX] = {1,3,5,6,7,9,10,11,22};

バイナリーサーチは、サーチ対象の中央を起点として、
右半分・左半分どちらにあるかを判定して、サーチ対象の位置を絞り込んでいきます。

leftとrightを下記のように初期値を定義して、

	int left = 0;
	int right = MAX - 1;

targetが、右半分・左半分どちらに位置するかをループ処理していきます。
targetが、leftとrightが隣り合うまでループ処理しすると、
leftかrightのどちらかにtargetが存在することになります。

	while(left + 1 != right){
		middle = (left + right) / 2;
		if(arr[middle] == target){
			return middle + 1;
		}else if(target < arr[middle]){
			right = middle;
		}else{
			left = middle;
		}
	}

途中でtargetが見つかればreturnし、最後までループ処理したら、
leftかright、targetがある方をreturnします。
targetがなければ-1をリターンしています。
※targetは0以上の整数としています。

	if(arr[left] == target){
		return left +1;
	}else if(arr[right] == target){
		return right + 1;
	}
	return -1;

サンプルコード

下記がサンプルコードになります。

$ cat sample.c 
#include <stdio.h>

#define MAX (9)
int arr[MAX] = {1,3,5,6,7,9,10,11,22};

int binarySearch(int target){
	int left = 0;
	int right = MAX - 1;
	int middle;
	
	while(left + 1 != right){
		middle = (left + right) / 2;
		if(arr[middle] == target){
			return middle + 1;
		}else if(target < arr[middle]){
			right = middle;
		}else{
			left = middle;
		}
	}
	if(arr[left] == target){
		return left +1;
	}else if(arr[right] == target){
		return right + 1;
	}
	return -1;
}


int main(){
	printf("%d\n", binarySearch(2));
	printf("%d\n", binarySearch(80));
	printf("%d\n", binarySearch(10));
	printf("%d\n", binarySearch(3));
	printf("%d\n", binarySearch(22));
	printf("%d\n", binarySearch(10));
	printf("%d\n", binarySearch(11));
	printf("%d\n", binarySearch(1));
	
	return 0;
}

下記が実行結果になります。

$ gcc -o sample sample.c
$ ./sample 
-1
-1
7
2
9
7
8
1