C++二分查找

悠悠 2024-03-17 09:52 41阅读 0赞

#### 二分查找 ####

###### 描述 ######

从小到大输入若干整数（不超过300），以-99999为结束符，然后再输入一个整数x，在前面的整数中用二分查找法查找x，若找到，显示数的下标（即从0开始的序号）；若找不到，显示-1。注意，不应使用别人写的库函数。‪‬‪‬‪‬‪‬‪‬‮‬‭‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬

###### 输入 ######

若干整数。‪‬‪‬‪‬‪‬‪‬‮‬‭‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬

###### 输出 ######

一个下标。‪‬‪‬‪‬‪‬‪‬‮‬‭‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬

###### 输入输出示例 ######

![在这里插入图片描述][05a1228c1acc42fb958bab54a55fb44d.png]

#include <iostream>
    #include <vector>
    using namespace std;
    int main() {
        
        vector<int> nums;
        int num;
        while (cin >> num && num != -99999) {
        
            nums.push_back(num);
        }
    
        int x;
        cin >> x;
    
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
        
            int mid = (left + right) / 2;
            if (nums[mid] == x) {
        
                cout << mid << endl;
                return 0;
            } else if (nums[mid] < x) {
        
                left = mid + 1;
            } else {
        
                right = mid - 1;
            }
        }
    
        cout << -1 << endl;
        return 0;
    }

#include <iostream>
    using namespace std;
    int binarySearch(int a[], int left, int right, int dest);
    int main() {
        
    	int a[310];
    	int i = 0;
    	int num;
    	while (cin >> num && num != -99999)
    		a[i++] = num;
    	int dest;
    	cin >> dest;
    	int idx = binarySearch(a, 0, i - 1, dest);
    	cout << idx << endl;
    	return 0;
    }
    
    int binarySearch(int a[], int left, int right, int dest) {
        
    	while (left <= right) {
         //只要数组还没空
    		int midIdx = (left + right) / 2; //就取中间值比较
    		int mid = a[midIdx];
    		if (dest > mid)	//中间值小了，说明目标数在右边，就把左端右移
    			left = midIdx + 1;
    		else if (dest < mid) //中间值大了，说明目标数在左边，就把右端左移
    			right = midIdx - 1;
    		else
    			return midIdx;//找到后就返回
    	}
    	return -1;
    
    }
    //二分查找必须是有序序列

**二分查找（Binary Search），也称为折半查找，是一种常用的查找算法。它将要查找的区间中间位置的元素与所要查找的元素进行比较，如果两个元素相等，则查找成功；如果中间位置的元素大于要查找的元素，则在左半部分区间中继续查找；如果中间位置的元素小于要查找的元素，则在右半部分区间中继续查找。依次类推，直到查找到要查找的元素，或者查找区间缩小为 0。**

下面是 C++ 实现二分查找的代码示例：

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    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;
    }
    
    int main() {
        int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int n = sizeof(arr) / sizeof(arr[0]);
        int x = 4;
        int result = binarySearch(arr, n, x);
        if (result == -1) {
            cout << "Element not found" << endl;
        } else {
            cout << "Element found at index " << result << endl;
        }
        return 0;
    }

**在上面的例子中，我们使用了 while 循环实现了二分查找。算法的时间复杂度是 O(log n)。注意到有时候二分查找可能会溢出，因此在计算 mid 时需要用 left + (right - left) / 2 替换 (left + right) / 2。**

[05a1228c1acc42fb958bab54a55fb44d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/2a001b37ed0f4d0581e4a303e0277a62.png