查找中间数

package com.viking.divide;

/**
 * 
 * @author viking
 * 
 *         查找中间数 有两个长度相等，按升序排列的数组，现要查找中间数 因为有两个中间数，返回偏小的那一个
 * 
 *         中间数是数组中大小处于中间的那个数
 * 
 *         基本思路，用而分查找的方法查找
 * 
 * 
 * 
 */
public class Middle {
	public static void main(String[] args) {
		int[] a = {15,  16, 23,27 };
		int[] b = {7, 10, 12,13 };
		int mid = findMiddle(a, b);
		System.out.println(mid);
	}

	public static int findMiddle(int[] a, int[] b) {
		int n = a.length;
		int amid = 0, bmid = 0;
		int alow = 0, blow = 0;
		int ahight = n - 1, bhight = n - 1;
		while (alow < ahight && blow < bhight) {
			amid = (alow + ahight) / 2;
			bmid = (blow + bhight) / 2;
			if (a[amid] > b[bmid]) {
				// 中间数会在 a的中 alow-amid半区和b的blow-bhight半区中
				ahight = amid;
				blow = bmid;
			} else {
				// 中间数会在 b的中 blow-bmid半区和a的alow-ahight半区中
				alow = amid;
				bhight = bmid;
			}
		}
		// 由于取整问题，下标总是指向偏小的数
		// a[amid+1]或者b[bmid+1]有可能是中间数
		// middle 肯定在a[amid] a[amid+1] b[bmid] b[bmid+1]这四个数中
		// 对amid bmid 进行修正
		if (amid + bmid + 1 == n - 2) {
			if (a[amid] > b[bmid]) {
				amid++;
			} else {
				bmid++;
			}
		} else if (amid + bmid + 2 == n - 2) {
			amid++;
			bmid++;
		}

		if (a[amid] > b[bmid]) {
			if (bmid < n && a[amid] > b[bmid + 1]) {
				// bmid+1才是偏小的那个中间数
				return b[bmid + 1];
			}
			return a[amid];
		} else {
			if (amid < n && b[bmid] > a[amid + 1]) {
				// amid+1才是偏小的那个中间数
				return a[amid + 1];
			}
			return b[bmid];
		}
	}
}