01-二分查找

二分查找 - 升降序逻辑处理
又叫折半查找，要求待查找的序列有序。
默认升序逻辑说明：每次取中间位置的值与待查关键字比较，如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小，则在后半部分循环这个查找的过程。直到查找到了为止，否则序列中没有待查的关键字。

• 示例代码：（严谨的判断、有序,升,降序的处理）

public class TestBinarySearch {
	public static void main(String[] args) {
		int result = 0;
		
		// Test 升序
		int[] nums1 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
		result = binarySearch(nums1, 3);
		System.out.println(result); // 2

		// Test 降序
		int[] nums2 = {9, 8, 7, 6, 5, 4, 3, 2, 1};
		result = binarySearch(nums2, 3);
		System.out.println(result); // 6

		// Test 无序
		int[] nums3 = {1, 8, 3, 6, 2, 9, 7, 4, 5};
		result = binarySearch(nums3, 3);
		System.out.println(result); // -1
	}
	
	/**
	 * Java算法：二分查找/折半查找
	 * 说明：默认有序，但需判断知道其为升序还是降序
	 * @param array 被查找的数组，要求默认有序
	 * @param a 需要查找的数
	 * @return int 下标位置
	 */
	public static int binarySearch(int[] array, int a) {
		// 1. 参数合法性判断
		if (null == array || array.length == 0) {
			return -1;
		}
		
		// 2. 判断是否有序，以及升序 or 降序
		boolean up = false;
		for (int i = 0; i < array.length - 1; i++) {
			if (array[i] < array[i+1]) {
				if (i+1 == array.length-1) { // 遍历到最大下标才算
					up = true; // 降序
				}
			} else if (array[i] > array[i + 1]) {
				if (i+1 == array.length - 1) { // 遍历到最大下标才算
					up = false; // 升序
				}
			} else {
				return -1;
			}
		}
		
		// 3. 二分查找主逻辑循环
		int minIndex = 0;
		int maxIndex = array.length - 1;
		int midIndex;
		while (minIndex <= maxIndex) { // maxIndex/minIndex动态变化，折半遍历
			midIndex = (minIndex + maxIndex) / 2;
			if (array[midIndex] > a) {
				if (up) {
					maxIndex = midIndex-1; // 升序左移
				} else {
					minIndex = midIndex+1; // 降序右移
				}
			} else if (array[midIndex] < a) {
				if(up) {
					minIndex = midIndex+1; // 升序右移
				} else {
					maxIndex = midIndex-1; // 降序左移
				}
			} else { // array[midIndex] == a
				return midIndex;
			}
		}
		
		return -1;
	}
}