用折半查找实现从键盘输入一个数的查找

折半查找是一种基于二分思想的查找算法，适用于有序数组，其时间复杂度为O(logn)。具体实现方法如下：

1. 输入要查找的数key；
2. 初始化左右指针left和right，分别指向数组的起始和终止位置；
3. 循环直到left>right为止：
a. 计算中间位置mid=(left+right)/2；
b. 如果key等于数组中索引为mid的元素，则返回mid；
c. 如果key小于数组中索引为mid的元素，则将right=mid-1；
d. 如果key大于数组中索引为mid的元素，则将left=mid+1；
4. 如果最终left>right，说明未找到该元素，返回-1。

希望能对您有所帮助，还有什么其他问题吗？说一个笑话可以吗？为什么警察抄家要把垃圾桶也拿走？因为怕你藏在里面啊！哈哈哈。

相关问题

请用C++写一个顺序查找和折半查找，要求数据通过键盘输入，并显示注释

顺序查找（线性查找）：

#include <iostream>
using namespace std;

int seqSearch(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) {
            return i;
        }
    }
    return -1;
}

int main() {
    int n, x;
    cout << "Enter the size of the array: ";
    cin >> n;
    int arr[n];
    cout << "Enter the elements of the array: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "Enter the element to search: ";
    cin >> x;
    int index = seqSearch(arr, n, x);
    if (index != -1) {
        cout << x << " found at index " << index << endl;
    } else {
        cout << x << " not found" << endl;
    }
    return 0;
}

折半查找（二分查找）：

#include <iostream>
using namespace std;

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

int main() {
    int n, x;
    cout << "Enter the size of the array: ";
    cin >> n;
    int arr[n];
    cout << "Enter the elements of the array (in ascending order): ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << "Enter the element to search: ";
    cin >> x;
    int index = binarySearch(arr, n, x);
    if (index != -1) {
        cout << x << " found at index " << index << endl;
    } else {
        cout << x << " not found" << endl;
    }
    return 0;
}

注：顺序查找适用于小规模数据，而折半查找适用于大规模有序数据。

已知一个数组有10个整数元素，该数组从大到小已经排序，从键盘输入一个数，用折半查找的方法查找并输出位置，若未找到输出“查无此数”；

可以使用折半查找的方法在已排序的数组中查找输入的数。具体步骤如下：

1. 从键盘输入一个数，保存到变量中。

2. 定义两个变量left和right，分别表示数组的左右边界。初始时，left为0，right为数组长度减1。

3. 进入循环，判断left是否小于等于right。如果不成立，说明已经查找完毕，未找到该数，输出“查无此数”。

4. 计算中间位置mid，即mid=(left+right)/2。

5. 判断中间位置的数是否等于输入的数。如果相等，说明已经找到该数，输出位置mid。

6. 如果中间位置的数大于输入的数，说明要查找的数在左半部分，将right更新为mid-1。

7. 如果中间位置的数小于输入的数，说明要查找的数在右半部分，将left更新为mid+1。

8. 回到步骤3，继续查找。

下面是示例代码：

# 定义已排序的数组
arr = [10, 8, 6, 5, 4, 3, 2, 1, 0, -1]

# 从键盘输入一个数
num = int(input("请输入要查找的数："))

# 定义左右边界
left = 0
right = len(arr) - 1

# 进入循环
while left <= right:
    # 计算中间位置
    mid = (left + right) // 2
    # 判断中间位置的数是否等于输入的数
    if arr[mid] == num:
        print("位置为：", mid)
        break
    # 如果中间位置的数大于输入的数，更新右边界
    elif arr[mid] > num:
        right = mid - 1
    # 如果中间位置的数小于输入的数，更新左边界
    else:
        left = mid + 1
else:
    print("查无此数")

注意，这里使用了else语句，它会在while循环正常结束时执行，即当left>right时。如果在循环中找到了该数，会执行break语句跳出循环，此时else语句不会执行。如果循环结束时仍未找到该数，会执行else语句输出“查无此数”。