Algorithms►算法

dichotomy-recursive

二分法作为比较基础的算法，虽然工作中不常使用，但是作为编程基础，还是很有必要整理下的，下面是二分法递归版本的代码，记录在blog，以备后面查看温习。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>

// 采用递归方法
int BSearch(int d[], int target, int low, int high)
{
    int m;
    if (low <=high)
    {
        m = (low + high)/2;
        if (d[m] > target)
        {
            return BSearch(d, target, low, m-1);
        }
        else if (d[m] < target)
        {
            return BSearch(d, target, m+1, high);
        }
        else
        {
            return m;
        }
    }
    return -1;
    
}
 
int  main(int argc, char *argv[])
{
	int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	int c = BSearch(a, 5, 0, 10);
	printf("index:%d\n", c);
}

Compile and Run

1
2
3
gcc main.c -o main
./main
index:4