二分查找

思想：
在有序且不重复的数组中， 选中间的值和目标值做对比， 比中间值大就从后半部分数据查找， 比中间值小从前半部分数据查找， 直到找到和目标值相等的中间值， 返回其下标；

代码实现

// 循环实现
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;
}

// 递归实现
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);

四个变体

// 变体一：查找第一个值等于给定值的元素
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;
}

// 变体二：查找最后一个值等于给定值的元素
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;
}

// 变体三：查找第一个大于等于给定值的元素
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;
}

// 变体四：查找最后一个小于等于给定值的元素
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;
}