思想：
在有序且不重復(fù)的數(shù)組中熔萧， 選中間的值和目標(biāo)值做對(duì)比， 比中間值大就從后半部分?jǐn)?shù)據(jù)查找洪唐， 比中間值小從前半部分?jǐn)?shù)據(jù)查找钻蹬， 直到找到和目標(biāo)值相等的中間值， 返回其下標(biāo)凭需；

代碼實(shí)現(xiàn)

// 循環(huán)實(shí)現(xiàn)
int binarySearch(int a[], int n, int target) {
    int low = 0;
    int high = n - 1;
    int mid = high / 2;
    while (low <= high) {
        if (a[mid] == target) {
            return mid;
        } else if (a[mid] > target) {
            high = mid - 1;
            mid = high / 2;
        } else {
            low = mid + 1;
            mid = low + ((high - mid) >> 1);
        }
    }
    return -1;
}

// 遞歸實(shí)現(xiàn)
int binarySearch1(int a[], int n, int target) {
    int low = 0;
    int high = n - 1;
    return binarySearch_recursive(a, low, high, target);
}

int binarySearch_recursive(int a[], int low, int high, int target) {
    // 遞歸終止條件
    while (low > high) {
        return -1;
    }
    int mid = low + ((high - low) >> 1);
    if (a[mid] == target) {
        return mid;
    } else if (a[mid] > target) {
        high = mid - 1;
        binarySearch_recursive(a, low, high, target);
    } else {
        low = mid + 1;
        binarySearch_recursive(a, low, high, target);
    }
    return -1;
}

使用

int a[] = {1, 2, 3, 4, 5, 6, 7 ,8};
    int num = sizeof(a) / sizeof(int);
    int index = binarySearch1(a, num, 4);
    printf("%d", index);

四個(gè)變體

// 變體一：查找第一個(gè)值等于給定值的元素
int binarySearch2(int a[], int n, int target) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (a[mid] == target) {
            if (low == 0 || a[mid - 1] != target) {
                return mid;
            } else {
                high = mid - 1;
            }
        } else if (a[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

// 變體二：查找最后一個(gè)值等于給定值的元素
int binarySearch3(int a[], int n, int target) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (a[mid] == target) {
            if (mid == n - 1 || a[mid + 1] != target) {
                return mid;
            } else {
                low = mid + 1;
            }
        } else if (a[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

// 變體三：查找第一個(gè)大于等于給定值的元素
int binarySearch4(int a[], int n, int target) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (a[mid] >= target) {
            if (mid == 0 || a[mid - 1] < target) {
                return mid;
            } else {
                high = mid - 1;
            }
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

// 變體四：查找最后一個(gè)小于等于給定值的元素
int binarySearch5(int a[], int n, int target) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (a[mid] <= target) {
            if (mid == n - 1 || a[mid + 1] > target) {
                return mid;
            } else {
                low = mid + 1;
            }
        } else {
            high = mid - 1;
        }
    }
    return -1;
}