二分查找，偏移循環二分查找

1.普通的二分查找
           

二分查找的關鍵是為了确定上下界，必須注意邊界，全開，全閉，半開半閉，統一就好
           

public static int search(int[] a, int key, int low, int hight) {
		int middle;

		while (low <= hight) {
			middle = ((hight - low) >> 1) + low;// 一定要加括号啊
			if (key == a[middle]) {
				return middle;
			} else if (key > a[middle]) {
				low = middle + 1;
			} else {
				hight = middle - 1;
			}
		}
		return -1;

	}
           

2. 具有偏移的二分查找

   比如：4,7,8,9,10,1,2,3

  在循環遞增數組中我們不能簡單地通過與數組中間元素的大小關系來确定要檢索的元素所落在的區間範圍。

  要确定範圍我們可以再加上要檢索的元素與數組兩端的元素的大小關系。 循環遞增數組有這麼一個性質

以數組中間元素将循環遞增數組劃分為兩部分則一部分為一個嚴格遞增數組

而另一部分為一個更小的循環遞增數組。當中間元素大于首元素時前半部分為嚴格遞增數組後半部分為循環遞增數組當中間元素小于首元素時前半部分為循環遞增數組後半部分為嚴格遞增數組。 記要檢索的元素為key數組的首元素為a[low]

中間元素為a[mid]末尾元素為a[high]。則當key不等于a[mid] 時     

1、a[mid] > a[low]即數組前半部分為嚴格遞增數組後半部分為循環遞增數組時若key小于a[mid]并且不小于a[low]時則key落在數組前半部分否則key落在數組後半部分。     

2、a[mid] < a[high]即數組前半部分為循環遞增數組後半部分為嚴格遞增數組時若key大于a[mid]并且不大于a[high]時則key落在數組後半部分否則key落在數組前半部分。

public static int search(int[] a, int key) {
		int low = 0;
		int hight = a.length - 1;
		int middle = 0;
		int pos = -1;// -1表示沒有查找到
		while (low <= hight) {
			System.out.println("low"+low);
			System.out.println("hight"+hight);
			middle = ((hight - low) >> 1) + low;
			System.out.println("middle:"+middle);
			if (key == a[middle]) {
				pos = middle;
				break;
			}
			if (a[middle] > a[low]) {// 前半部分是遞增的
				if (key > a[low] && key < a[middle]) {
					hight = middle - 1;
				} else {
					low = middle + 1;
				}
			} else {
				if (key > a[middle] && key < a[hight]) {
					low = middle + 1;
				} else {
					hight = middle - 1;
				}
			}
		}
		return pos;

	}