数据结构折半查找例题_查找-第9章-《数据结构题集》习题解析-严蔚敏吴伟民版...

好的，折半查找也叫二分查找，是一种常见的查找算法。下面以一个例题来说明：

【例题】在一个有序数组中查找一个数，如果存在则返回下标，如果不存在则返回-1。

解题思路：

1. 定义变量left和right分别表示数组的左右边界，初始时left=0，right=n-1，其中n为数组的长度。

2. 循环执行以下步骤：

1）计算中间位置mid=(left+right)/2；

2）如果中间位置的元素等于要查找的数，则返回mid；

3）如果中间位置的元素大于要查找的数，则说明要查找的数在数组的左半部分，将right更新为mid-1；

4）如果中间位置的元素小于要查找的数，则说明要查找的数在数组的右半部分，将left更新为mid+1；

5）如果left>right，则说明要查找的数不存在于数组中，返回-1。

代码实现如下：

int binarySearch(int a[], int n, int x) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (a[mid] == x) {
            return mid;
        } else if (a[mid] > x) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

在上面的代码中，a表示有序数组，n为数组长度，x为要查找的数。在循环中，如果找到了要查找的数，则返回它的下标；如果找不到，则返回-1。

希望能对你有所帮助。