算法 第四版 1.4.22 仅用加减实现的二分查找

利用裴波那契数列来分区间

	public static boolean MihaiPatrascuSearch(int[] a, int key){Arrays.sort(a);int F1=1, F2=1;while(F2<=a.length){int temp=F2;F2 = F1+F2;F1 = temp;}int lo = 0, hi = a.length-1; // lo = i, hi = Fkwhile(lo<=hi){int mid = lo + F2 - F1 - 1; // mid = i + Fk-2 , (Fk最小为1， 只能[0,1] 所以减去1)if(a[mid] == key) return true;else if(a[mid]>key){ // [i, i+Fk-2]hi = lo + F2 - F1;F2 = F2 - F1;   //Fk = Fk-2F1 = F1 - F2;}else if(a[mid]<key){ // [i, i+Fk-2+Fk-1]hi = Math.min(hi, lo+F2);lo = lo + F2 - F1;int temp = F1;  //Fk = Fk-1F1 = F2 - F1;F2 = temp;}}return false;}