0%

二分查找

发表于 更新于

二分查找的前提是所查找的数组已经有序。在查找过程中，

每次取出中间的元素，与目标数值比较，若相等则直接返回；

若不等，则根据排序规则在一侧中继续查找，直到这一侧元素仅剩一个时，

若与目标元素相等，则直接返回；否则表明数组中没有待查找元素。

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
33
34
35
36
37
38
39
40
41
42
43
44
public class BinarySearch {
	
	// 二分查找的前提是所查找的数组已经有序。在查找过程中，
	// 每次取出中间的元素，与目标数值比较，若相等则直接返回；
	// 若不等，则根据排序规则在一侧中继续查找，直到这一侧元素仅剩一个时，
	// 若与目标元素相等，则直接返回；否则表明数组中没有待查找元素。
	public static int binarySearch(int[] array, int target) {
		int startIndex = 0, 
			endIndex = array.length - 1,
			middleIndex = (endIndex - startIndex) / 2 + startIndex;
		
		while(startIndex <= endIndex) {
			// 根据以下方法定义中间元素，会导致中间元素总会偏左侧
			// 例如两个元素时，有 1 / 2 + startIndex = startIndex
			// 当连续若干个元素相等时，总会找到偏右侧的
			middleIndex = (endIndex - startIndex) / 2 + startIndex;
			if (array[middleIndex] == target) {
				return middleIndex;
			} else if (array[middleIndex] < target) {
				startIndex = middleIndex + 1;    // 假设数组正序，中间元素比目标元素小，则在右侧（更大一侧）继续查找
			} else {
				endIndex = middleIndex - 1;    // 大于目标元素，则在左侧（更小一侧）查找
			}
		}
		
		return -1;
	}
	
	public static void main(String[] args) {
		int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
		System.out.println(BinarySearch.binarySearch(a, 1));
		System.out.println(BinarySearch.binarySearch(a, 2));
		System.out.println(BinarySearch.binarySearch(a, 3));
		System.out.println(BinarySearch.binarySearch(a, 4));
		System.out.println(BinarySearch.binarySearch(a, 5));
		System.out.println(BinarySearch.binarySearch(a, 6));
		System.out.println(BinarySearch.binarySearch(a, 7));
		System.out.println(BinarySearch.binarySearch(a, 8));
		System.out.println(BinarySearch.binarySearch(a, 9));
		System.out.println(BinarySearch.binarySearch(a, 10));
		System.out.println(BinarySearch.binarySearch(a, 11));
	}

}