/* 每次二分总会使至少半边有序,例如20 25 1 3 4 5| 6 7 8 9 10 或者 18 20 | 25 1 2,每次我们只分析有序的那半边 */ #include <iostream> using namespace std; int search(int a[], int lhs, int rhs, int x) { while(lhs <= rhs) { int mid =(lhs + rhs) >> 1; if(a[mid] == x) return mid; if(a[mid] >= a[lhs]) //如果左半边有序 { if(x <= a[mid] && x >= a[lhs]) //如果在左半边 { rhs = mid - 1; //好办了 } else //如果不在左半边,去右半边 { lhs = mid + 1; } } else //如果右半边有序,其余同上 { if(x > a[mid] && x <= a[lhs]) { //rhs = mid - 1; lhs = mid + 1; } else { //lhs = mid + 1; rhs = mid - 1; } } } return -1; } int main(void) { int a[12] = { 15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14 }; cout << search(a, 0, 11, 5) << endl; return 0; }