【C言語】二分探索(binary seach)

二分探索(binary seach)を実装すると次のようになる。

次のコードをbinarySearch.cとする。

環境
windows10(64bit)
Borland C++ 5.5.1 for Win32

#include <stdio.h>

int binarySearch(int arr[], int n, int target) {

    int left = 0;
    int right = n - 1;
    int ctr = 0;

    while (left <= right) {

        int mid = (left + right) / 2;

        ctr += 1;

        printf("ctr = %d, left = %d,right = %d,mid = %d\n",ctr, left,right,mid);

        if (target == arr[mid]){
            return mid;
        }else if (target < arr[mid]){
            right = mid - 1;
            printf("right(= mid - 1) = %d\n",right);
        }else{
           left = mid + 1;
           printf("left(= mid + 1) = %d\n",left);
        }

    }

    return -1;  // Target not found
}

int main() {

    int arr[] = {13, 26, 41, 52, 73, 85, 95};
    int n = sizeof(arr) / sizeof(arr[0]);
    int result;
    int target;

    printf("配列に数字nがあるかを二分探索で調べる。\n");
    printf("数字nを入力せよ\n");

    scanf("%d", &target);
    printf("target = %d\n",target);
	
    result = binarySearch(arr, n, target);
    
    if (result == -1){
        printf("Target not found\n");
    }else{
        printf("Target found at index: %d, arr[%d] = %d \n", result, result, arr[result]);
    }

    return 0;

}

コンパイルして実行する。

c:\coco_c>bcc32 binarySearch.c
Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000 Borland
binarySearch.c:
Turbo Incremental Link 5.00 Copyright (c) 1997, 2000 Borland

c:\coco_c>binarySearch.exe
配列に数字nがあるかを二分探索で調べる。
数字nを入力せよ
13
target = 13
ctr = 1, left = 0,right = 6,mid = 3
right(= mid - 1) = 2
ctr = 2, left = 0,right = 2,mid = 1
right(= mid - 1) = 0
ctr = 3, left = 0,right = 0,mid = 0
Target found at index: 0, arr[0] = 13

c:\coco_c>binarySearch.exe
配列に数字nがあるかを二分探索で調べる。
数字nを入力せよ
26
target = 26
ctr = 1, left = 0,right = 6,mid = 3
right(= mid - 1) = 2
ctr = 2, left = 0,right = 2,mid = 1
Target found at index: 1, arr[1] = 26

c:\coco_c>binarySearch.exe
配列に数字nがあるかを二分探索で調べる。
数字nを入力せよ
41
target = 41
ctr = 1, left = 0,right = 6,mid = 3
right(= mid - 1) = 2
ctr = 2, left = 0,right = 2,mid = 1
left(= mid + 1) = 2
ctr = 3, left = 2,right = 2,mid = 2
Target found at index: 2, arr[2] = 41

c:\coco_c>binarySearch.exe
配列に数字nがあるかを二分探索で調べる。
数字nを入力せよ
52
target = 52
ctr = 1, left = 0,right = 6,mid = 3
Target found at index: 3, arr[3] = 52

c:\coco_c>binarySearch.exe
配列に数字nがあるかを二分探索で調べる。
数字nを入力せよ
73
target = 73
ctr = 1, left = 0,right = 6,mid = 3
left(= mid + 1) = 4
ctr = 2, left = 4,right = 6,mid = 5
right(= mid - 1) = 4
ctr = 3, left = 4,right = 4,mid = 4
Target found at index: 4, arr[4] = 73

c:\coco_c>binarySearch.exe
配列に数字nがあるかを二分探索で調べる。
数字nを入力せよ
85
target = 85
ctr = 1, left = 0,right = 6,mid = 3
left(= mid + 1) = 4
ctr = 2, left = 4,right = 6,mid = 5
Target found at index: 5, arr[5] = 85

c:\coco_c>binarySearch.exe
配列に数字nがあるかを二分探索で調べる。
数字nを入力せよ
95
target = 95
ctr = 1, left = 0,right = 6,mid = 3
left(= mid + 1) = 4
ctr = 2, left = 4,right = 6,mid = 5
left(= mid + 1) = 6
ctr = 3, left = 6,right = 6,mid = 6
Target found at index: 6, arr[6] = 95

c:\coco_c>binarySearch.exe
配列に数字nがあるかを二分探索で調べる。
数字nを入力せよ
100
target = 100
ctr = 1, left = 0,right = 6,mid = 3
left(= mid + 1) = 4
ctr = 2, left = 4,right = 6,mid = 5
left(= mid + 1) = 6
ctr = 3, left = 6,right = 6,mid = 6
left(= mid + 1) = 7
Target not found

c:\coco_c>binarySearch.exe
配列に数字nがあるかを二分探索で調べる。
数字nを入力せよ
1
target = 1
ctr = 1, left = 0,right = 6,mid = 3
right(= mid - 1) = 2
ctr = 2, left = 0,right = 2,mid = 1
right(= mid - 1) = 0
ctr = 3, left = 0,right = 0,mid = 0
right(= mid - 1) = -1
Target not found

c:\coco_c>

binarySearch関数の別解。
binarySearch関数は「C言語による最新アルゴリズム時点 奥村晴彦著」に載っていた。
この別解は分かりずらいな。
binarySearch.c

#include <stdio.h>

int binarySearch(int arr[], int n, int target) {
	int left = 0;
	int right = n - 1;
	int mid;
	int ctr = 0;

	while(left < right){
		ctr += 1;
		mid = (left + right) / 2;
		if(arr[mid] < target) left = mid + 1; else right = mid;
		printf("ctr = %d, left = %d,right = %d, mid = %d\n",ctr, left, right, mid);
	}

	if (arr[left] == target) return left;
	return -1;

}

int main() {

	int arr[] = {13, 26, 41, 52, 73, 85, 95};
	int n = sizeof(arr) / sizeof(arr[0]);
	int result;
	int target;

	printf("配列に数字nがあるかを二分探索で調べる。\n");
	printf("数字nを入力せよ\n");

	scanf("%d", &target);
	printf("target = %d\n",target);

	result = binarySearch(arr, n, target);

	if (result == -1){
		printf("Target not found\n");
	}else{
		printf("Target found at index: %d, arr[%d] = %d \n", result, result, arr[result]);
	}

	return 0;

}

コンパイルして実行する。

c:\coco_c>bcc32 binarySearch.c
Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000 Borland
binarySearch.c:
Turbo Incremental Link 5.00 Copyright (c) 1997, 2000 Borland

c:\coco_c>binarySearch.exe
配列に数字nがあるかを二分探索で調べる。
数字nを入力せよ
13
target = 13
ctr = 1, left = 0,right = 3, mid = 3
ctr = 2, left = 0,right = 1, mid = 1
ctr = 3, left = 0,right = 0, mid = 0
Target found at index: 0, arr[0] = 13

c:\coco_c>binarySearch.exe
配列に数字nがあるかを二分探索で調べる。
数字nを入力せよ
26
target = 26
ctr = 1, left = 0,right = 3, mid = 3
ctr = 2, left = 0,right = 1, mid = 1
ctr = 3, left = 1,right = 1, mid = 0
Target found at index: 1, arr[1] = 26

c:\coco_c>binarySearch.exe
配列に数字nがあるかを二分探索で調べる。
数字nを入力せよ
41
target = 41
ctr = 1, left = 0,right = 3, mid = 3
ctr = 2, left = 2,right = 3, mid = 1
ctr = 3, left = 2,right = 2, mid = 2
Target found at index: 2, arr[2] = 41

c:\coco_c>binarySearch.exe
配列に数字nがあるかを二分探索で調べる。
数字nを入力せよ
52
target = 52
ctr = 1, left = 0,right = 3, mid = 3
ctr = 2, left = 2,right = 3, mid = 1
ctr = 3, left = 3,right = 3, mid = 2
Target found at index: 3, arr[3] = 52

c:\coco_c>binarySearch.exe
配列に数字nがあるかを二分探索で調べる。
数字nを入力せよ
73
target = 73
ctr = 1, left = 4,right = 6, mid = 3
ctr = 2, left = 4,right = 5, mid = 5
ctr = 3, left = 4,right = 4, mid = 4
Target found at index: 4, arr[4] = 73

c:\coco_c>binarySearch.exe
配列に数字nがあるかを二分探索で調べる。
数字nを入力せよ
85
target = 85
ctr = 1, left = 4,right = 6, mid = 3
ctr = 2, left = 4,right = 5, mid = 5
ctr = 3, left = 5,right = 5, mid = 4
Target found at index: 5, arr[5] = 85

c:\coco_c>binarySearch.exe
配列に数字nがあるかを二分探索で調べる。
数字nを入力せよ
95
target = 95
ctr = 1, left = 4,right = 6, mid = 3
ctr = 2, left = 6,right = 6, mid = 5
Target found at index: 6, arr[6] = 95

c:\coco_c>binarySearch.exe
配列に数字nがあるかを二分探索で調べる。
数字nを入力せよ
100
target = 100
ctr = 1, left = 4,right = 6, mid = 3
ctr = 2, left = 6,right = 6, mid = 5
Target not found

c:\coco_c>binarySearch.exe
配列に数字nがあるかを二分探索で調べる。
数字nを入力せよ
1
target = 1
ctr = 1, left = 0,right = 3, mid = 3
ctr = 2, left = 0,right = 1, mid = 1
ctr = 3, left = 0,right = 0, mid = 0
Target not found

c:\coco_c>

• 
• Tweet

• C言語