1010: 折半查找的实现

折半查找（Binary Search）是一种在有序数组中查找特定元素的算法，其基本思想是将查找区间不断折半缩小，直到找到目标元素或者查找区间为空为止。

以下是折半查找的实现代码：

// 在有序数组 arr 中查找元素 x，返回元素所在下标（从 0 开始计数），若不存在返回 -1
int binarySearch(int arr[], int n, int x) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x) {
            return mid;
        } else if (arr[mid] < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

其中，变量 `left` 和 `right` 分别表示查找区间的左右边界，初始时左边界为 0，右边界为数组长度减一。在每一轮循环中，首先计算中间位置 `mid`，然后将目标值 `x` 与 `arr[mid]` 进行比较，若相等则直接返回下标 `mid`，否则根据大小关系更新左右边界，继续缩小查找区间。如果最终查找区间变为空，则说明目标值不存在于数组中，返回 -1。

相关问题

数据结构折半查找实现

折半查找（二分查找）是一种查找有序数组中某一特定元素的算法。它通过将待查找区间不断缩小为一半来进行查找，直到找到目标元素或确定目标元素不存在为止。

具体实现过程如下：
1. 确定待查找的有序数组和目标元素。
2. 初始化两个指针，分别指向数组的第一个和最后一个元素。
3. 循环执行以下操作，直到找到目标元素或者确定目标元素不存在为止：
a. 求出中间元素的下标，即 (left + right) / 2。
b. 如果中间元素等于目标元素，则查找成功并返回中间元素的下标。
c. 如果中间元素大于目标元素，则将右边界指针 right 更新为 mid - 1。
d. 如果中间元素小于目标元素，则将左边界指针 left 更新为 mid + 1。
4. 如果待查找区间不存在目标元素，则查找失败。

编写函数实现折半查找Python

折半查找（Binary Search）是一种常用的查找法，它适用于有序数组。下面是用Python编写实现折半查找的函数：

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

这个函数接受两个参数，一个是有序数组 `arr`，另一个是要查找的目标值 `target`。函数使用两个指针 `low` 和 `high` 来表示查找范围的左右边界。在每次循环中，计算中间位置 `mid`，然后将目标值与中间位置的元素进行比较。如果相等，则返回中间位置；如果目标值小于中间位置的元素，则在左半部分继续查找；如果目标值大于中间位置的元素，则在右半部分继续查找。如果最终没有找到目标值，则返回 -1。