算法 之 分治 - 二分搜索

回忆一下二分搜索，将一个给定的元素x与一个已排序数组A[low...high]的中间元素作比较，

如果x<A[mid] ( mid=⌊(low + high)/2⌋ ) ，则不考虑A[mid...high]，而对A[low...mid-1]重复实施相同的方法。

类似地，如果x>A[mid]，就对A[mid+1...high]重复实施相同的方法。

这个就是今天介绍的著名的二分搜索算法。

 

过程  BinarySearch

输入  按非降序排列的n个元素的数组A[1...n]和元素x

输出  如果x=A[j]，则输出j；否则输出-1

 

算法描述  binarysearch(low, high)

if low > high then return -1

else

    mid ← ⌊(low + high) / 2⌋

    if x = A[mid] then return mid

    else if x < A[mid] then return binarysearch(low, mid - 1)

    else return binarysearch(mid + 1, high)

end if

 

这个算法比较简单，大家可以估算一下它的时间复杂性是 log n，下面是这个算法的 Java 实现：

 

DivideAndConquer.java 包含实现 BinarySearch 算法的类：

public class DivideAndConquer
{
	public static int binarySearch(int[] array, int value, int low, int high)
	{
		if (low > high)
			return -1;

		int middle = (low + high) / 2;
		
		if (value == array[middle])
		{
			return middle;
		}
		else if (value < array[middle])
		{
			return binarySearch(array, value, low, middle - 1);
		}
		else
		{
			return binarySearch(array, value, middle + 1, high);
		}
	}
}

 

Program.java 包含程序的入口方法，这里面还对传入的数组进行了一次冒泡排序，来保证传入的数组是有序的：

public class Program
{
	public static void main(String[] args)
	{
		int[] array = new int[] { 332, 566, 51, 70, 98, 19, 24, 637,
			53456, 3321, -235, -34, 5, 45, 77, 36 };
		
		bubbleSort(array);
		
		System.out.print("Initialize sorted array: ");
		for (int i : array)
		{
			System.out.printf("%d ", i);
		}
		
		int valueToBeFound = 70;
		int index = DivideAndConquer.binarySearch(
			array, valueToBeFound, 0, array.length - 1);
		System.out.printf("\n%d is found at position %d.", valueToBeFound, index);
	}

	private static void bubbleSort(int[] array)
	{
		for (int i = 0; i < array.length; i++)
		{
			for (int j = array.length - 1; j > i; j--)
			{
				if (array[i] > array[j])
				{
					// 交换array[i]和array[j]的位置
					array[i] = array[i] + array[j];
					array[j] = array[i] - array[j];
					array[i] = array[i] - array[j];
				}
			}
		}
	}
}