讲一遍C++中的二分查找

二分查找是一种常见的查找算法，也称为折半查找。它的前提是数据必须是有序的，每次查找都取中间位置的值与目标值进行比较，如果中间位置的值比目标值大，则在左半部分继续查找；如果中间位置的值比目标值小，则在右半部分继续查找，直到找到目标值或者查找区间为空为止。

以下是C++中的二分查找代码实现：

int binarySearch(int nums[], int size, int target) {
    int left = 0;
    int right = size - 1; // 注意这里是 size - 1
    while (left <= right) {
        int middle = left + ((right - left) / 2);
        if (nums[middle] > target) {
            right = middle - 1;
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else {
            return middle;
        }
    }
    // 没找到就返回-1
    return -1;
}

在这个实现中，我们使用了一个while循环来不断缩小查找区间，直到找到目标值或者查找区间为空为止。每次循环中，我们都取中间位置的值与目标值进行比较，并根据比较结果来缩小查找区间。

相关问题

在C++中如何实现一个线性表类，并包括顺序查找和二分查找方法？请结合面向对象的编程思想提供示例代码。

在C++中实现线性表类并通过面向对象的编程思想，你可以参考这份资料：《数据结构算法实验：C++实现线性表、查找、排序》。这本书将为你提供关于线性表、查找和排序算法的详细实验指导，帮助你更好地理解和实现这些数据结构和算法。

参考资源链接：[数据结构算法实验：C++实现线性表、查找、排序](https://wenku.csdn.net/doc/479xibeoha?spm=1055.2569.3001.10343)

首先，你需要定义一个线性表类，比如`SeqList`，并包含基本的操作如插入、删除、获取数据等。类的定义中应当包含数据成员来存储线性表的元素和大小，以及相应的成员函数来实现这些操作。例如，顺序查找方法可以遍历数组直到找到目标元素或遍历完所有元素。而二分查找则要求线性表是有序的，通过不断将查找区间缩小来快速定位目标元素的位置。

下面是一个简化版的`SeqList`类的实现框架和查找方法的示例代码：（代码略）

在这个示例中，`SeqList`类使用数组来存储元素，并提供了插入、删除和查找等成员函数。顺序查找方法`SequentialSearch`遍历数组元素来查找目标，而`BinarySearch`方法则利用二分查找算法来提高查找效率。

通过本实验的学习，你将掌握如何将数据结构和算法应用于C++程序中，同时加深对面向对象编程的理解。为了进一步提升你的实践能力，建议详细阅读《数据结构算法实验：C++实现线性表、查找、排序》这本书，其中详细介绍了线性表的实现以及顺序查找和二分查找的完整示例代码，还有其他数据结构和算法的实现方法，为你的编程之路奠定坚实的基础。

参考资源链接：[数据结构算法实验：C++实现线性表、查找、排序](https://wenku.csdn.net/doc/479xibeoha?spm=1055.2569.3001.10343)

将一个数组里的元素在另一个数组中查找并定位

当你想在一个数组中查找另一个数组中的特定元素，并找到它的位置时，这通常涉及到线性搜索或更高效的算法，如二分查找（如果数组已排序）。这里我将介绍两种常见方法：

1. **线性搜索**（遍历法）：
这是最基础的方法，对于未排序的数组，你可以逐个比较每个元素，直到找到目标值或遍历完整个数组。这个过程的时间复杂度为 O(n)，其中 n 是第一个数组的长度。

int linearSearch(int arr1[], int arr2[], int target, int m) {
    for (int i = 0; i < m; ++i) {
        if (arr1[i] == target) {
            return i;
        }
    }
    return -1; // 如果找不到目标值，返回 -1 或者你想用的其他标志表示不存在
}

2. **二分查找**（适用于有序数组）：
对于已经排序的数组，你可以使用二分查找，其时间复杂度为 O(log n)。但前提是你必须确保第一个数组是按升序排列的，且包含第二个数组的所有可能值。

int binarySearch(int arr1[], int left, int right, int target, int m) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr1[mid] == target) {
            return mid;
        } else if (arr1[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

使用时，你需要先对 `arr1` 进行排序，然后调用上述函数。

如果你有一个未排序的数组，但是希望知道目标元素在原数组中首次出现的位置（不考虑重复），可以使用哈希表或集合（如果可用）来提高查找速度，但这种方法通常不是 C++ 标准库的一部分。