408数据结构算法-2011

#include <iostream>

using namespace std;

int mSearch(int *A, int *B, int n) {
    int s1, d1, m1, s2, d2, m2;
    s1 = 0;
    d1 = n - 1;
    s2 = 1;
    d2 = n - 1;
    while (s1 != d1 || s2 != d2) {
        m1 = (s1 + d1) / 2;
        m2 = (s2 + d2) / 2;
        if (A[m1] == B[m2])return A[m1];
        if (A[m1] < B[m2]) {
            if ((s1 + d1) % 2 == 0) {
                s1 = m1;
                d2 = m2;
            } else {
                s1 = m1 + 1;
                d2 = m2;
            }
        } else {
            if ((s1 + d1) % 2 == 0) {
                s2 = m2;
                d1 = m1;
            } else {
                s2 = m2 + 1;
                d1 = m1;
            }
        }
    }
    return A[s1] < B[s2] ? A[s1] : B[s2];
}

int mSearch2(int *A, int *B, int n) {
    int mid = (int) (2 * n + 1) / 2;
    int mA = 0, mB = 0;
    bool flag = false;
    for (int i = 0; i < mid; i++) {
        if (A[mA] < B[mB]) {
            mA++;
            flag = true;
        } else {
            mB++;
            flag = false;
        }
    }
    return flag ? A[--mA] : B[--mB];
}

int main() {
    int array1[] = {1, 9, 11, 17, 19};
    int array2[] = {2, 4, 7, 8, 20};
    cout << mSearch(array1, array2, 5) << endl;
    cout << mSearch2(array1, array2, 5) << endl;
}
// 8 8