查找算法

发表于

      本文集中了两种查找算法:顺序查找算法与二分查找算法，其中二分查找算法又有两种实现方式，分别为递归查找与迭代查找。

顺序查找算法

C++ Code

1
2
3
4
5
6
7
8
9
int OrderFind(int* a,int n, int x)
{
	for (int i = 0; i < n; i++)
	{
		if (a[i] == x)
			return i;
	}
	return -1;
}

C# Code

1
2
3
4
5
6
7
8
9
10
public int OrderFind(int[] a, int x)
{
    int count = a.Length;
    for (int i = 0; i < count; i++)
    {
        if (a[i] == x)
            return i;
    }
    return -1;
}

Java Code

1
2
3
4
5
6
7
8
9
10
public int OrderFind(int[] a, int x)
{
    int count = a.length;
    for (int i = 0; i < count; i++)
    {
        if (a[i] == x)
            return i;
    }
    return -1;
}

二分查找(对半)算法

C++ Code

1
2
3
4
5
6
7
8
9
10
11
//二分查找递归算法
int BinarySearch(int* a, int x, int low, int high)
{
	int mid = (low+high)/2;
	if (low <= high)
	{
		if (a[mid] < x) mid = BinarySearch(a, x, mid + 1, high);
		else if (x < a[mid]) mid = BinarySearch(a, x, low, mid - 1);
	}
	return mid;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//二分查找迭代算法
int BinarySearch(int* a,int n, int x)
{
	int low = 0, high = n - 1,mid=-1;
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (x < a[mid]) high = mid - 1;
		else if (x > a[mid]) low = mid + 1;
		else return mid;
	}
	if (a[mid] != x) mid = -1;
	return mid;
}

C# Code

1
2
3
4
5
6
7
8
9
10
11
//二分查找递归算法
public int BinarySearch(int[] a, int x, int low, int high)
{
    int mid = (low+high)/2;
    if (low <= high)
    {
        if (a[mid] < x) mid = BinarySearch(a, x, mid + 1, high);
        else if (x < a[mid]) mid = BinarySearch(a, x, low, mid - 1);
    }
    return mid;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//二分查找迭代算法
public int BinarySearch(int[] a, int x)
{
    int count = a.Length;
    int low = 0, high = count - 1,mid=-1;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (x < a[mid]) high = mid - 1;
        else if (x > a[mid]) low = mid + 1;
        else return mid;
    }
    if (a[mid] != x) mid = -1;
    return mid;
}

Java Code

1
2
3
4
5
6
7
8
9
10
11
//二分查找递归算法
public int BinarySearch(int[] a, int x, int low, int high)
{
    int mid = (low+high)/2;
    if (low <= high)
    {
        if (a[mid] < x) mid = BinarySearch(a, x, mid + 1, high);
        else if (x < a[mid]) mid = BinarySearch(a, x, low, mid - 1);
    }
    return mid;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//二分查找迭代算法
public int BinarySearch(int[] a, int x)
{
    int count = a.length;
    int low = 0, high = count - 1,mid=-1;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (x < a[mid]) high = mid - 1;
        else if (x > a[mid]) low = mid + 1;
        else return mid;
    }
    if (a[mid] != x) mid = -1;
    return mid;
}

反馈请点击: