/*
每次二分总会使至少半边有序,例如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;
}
详细解决方案
Q9.3
热度:44 发布时间:2024-01-15 21:19:48.0
相关解决方案