二分查找

普通二分查找

• 只能在有序数组查找

// 1、3、5、7、9、10 
int binary_search(int *arr, int n, int x) {
    int head = 0, tail = n - 1, mid;
    while (head <= tail) {
        mid = (head + tail) >> 1;
        if (arr[mid] == x) return mid;
        if (arr[mid] > x) tail = mid - 1;
        else head = mid + 1;
    }
    return -1;
}

特殊情况1

• 数组为11111110000000类型的，查找最后一个1位置

//111111000000
int binary_search1(int *arr, int n) {
    int head = -1, tail = n - 1, mid;
    while (tail > head) {
        mid = (head + tail + 1) >> 1;
        if (arr[mid] == 1) head = mid;
        else tail = mid - 1;
    }
    return head;
}

特殊情况二

• 数组为0000000111111111类型的，查找第一个1位置

//00000000111111
int binary_search2(int *arr, int n) {
    int head = 0, tail = n - 1, mid;
    while (head < tail) {
        mid = (tail + head) >> 1;
        if (arr[mid] == 1) tail = mid;
        else head = mid + 1;
    }
    return head == n ? -1 : head;
}

测试

#include <stdio.h>

#define exp 1e-6
//精度值 
#define P(func) {\
    printf("%s = %d\n", #func, func);\
}

// 1、3、5、7、9、10 
int binary_search(int *arr, int n, int x) {
    int head = 0, tail = n - 1, mid;
    while (head <= tail) {
        mid = (head + tail) >> 1;
        if (arr[mid] == x) return mid;
        if (arr[mid] > x) tail = mid - 1;
        else head = mid + 1;
    }
    return -1;
}

//111111000000
int binary_search1(int *arr, int n) {
    int head = -1, tail = n - 1, mid;
    while (tail > head) {
        mid = (head + tail + 1) >> 1;
        if (arr[mid] == 1) head = mid;
        else tail = mid - 1;
    }
    return head;
}

//00000000111111
int binary_search2(int *arr, int n) {
    int head = 0, tail = n - 1, mid;
    while (head < tail) {
        mid = (tail + head) >> 1;
        if (arr[mid] == 1) tail = mid;
        else head = mid + 1;
    }
    return head == n ? -1 : head;
}

int main() {
    int arr1[10] = {1, 3, 4, 5, 7, 9, 10, 15, 18, 21};
    int arr2[10] = {1, 1, 1, 1, 1, 1, 0, 0, 0, 0};
    int arr3[10] = {0, 0, 0, 0, 0, 0, 1, 1, 1, 1};
    P(binary_search(arr1, 10, 15));
    P(binary_search1(arr2, 10));
    P(binary_search2(arr3, 10));    
    return 0;
}