#include <stdio.h>
#define P(func, ar, m, x) ({                printf("%s => %d == %d\n", #func, x, func(ar, m, x));})

int binary_search(int *ar, int m, int x) {
        int mid = (m - 1) >> 1, min = 0, max = m - 1;
        for (; min <= max && ar[mid] != x; mid = (min + max) >> 1)
                ar[mid] > x && (max = mid - 1, 1) || (min = mid + 1);
        return ar[mid] ^ x ? -1 : mid;
}

//全01时，查找最后一个1
int binary_search1(int *ar, int m, int x) {
        int mid = m >> 1, min = -1, max = m - 1;
        for (; min < max; mid = (min + max + 1) >> 1)
                ar[mid] && (min = mid) || (max = mid - 1);
        return min;
}

//全01时，查找第一个1
int binary_search2(int *ar, int m, int x) {
        int mid = m >> 1, min = 0, max = m;
        for (; min < max; mid = (max + min) >> 1)
                ar[mid] && (max = mid) || (min = mid + 1);
        return max ^ m ? max : -1;
}
int main() {
        int ar12[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        int ar[] = {1, 2, 3, 4, 11, 12, 13, 14, 15, 16}, ar1[] = {1, 1, 1, 1, 0, 0, 0, 0, 0, 0}, ar2[] = {0, 0, 0, 0, 1, 1, 1, 1, 1, 1};
        P(binary_search, ar, 10, 17);
        P(binary_search, ar, 10, 15);
        P(binary_search1, ar12, 10, 1);
        P(binary_search1, ar1, 10, 1);
        P(binary_search2, ar12, 10, 1);
        P(binary_search2, ar2, 10, 1);
        return 0;
}

二分查找，折半查找，特殊情况二分查找