折半查找--减治法

r囧r小猫 2024-03-17 09:53 54阅读 0赞

#### 折半查找–减治法 ####

‪‬‪‬‪‬‪‬‪‬‮‬‭‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬

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

使用折半查找法在有序序列（升序或降序）中，按值查找记录。若查找成功，返回记录在序列中的位置（位序，从1开始），若查找失败，返回0。‪‬‪‬‪‬‪‬‪‬‮‬‭‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬

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

输入序列长度‪‬‪‬‪‬‪‬‪‬‮‬‭‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬  
输入序列‪‬‪‬‪‬‪‬‪‬‮‬‭‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬  
输入查找的值‪‬‪‬‪‬‪‬‪‬‮‬‭‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‪‬

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

输出查找结果  
![在这里插入图片描述][c29e4aa36381412e8059548da65798d5.png]  
![在这里插入图片描述][f08af72824b040638438142821c92f49.png]

#include <iostream>
    #include <cstdio>
     
    using namespace std;
     
    int BinSearch(int r[], int n, int k)
    {
        
    	int mid, low = 0, high = n - 1;
    	while (low <= high)
    	{
        
    		mid = (low + high) / 2;
    		if (k < r[mid]) high = mid - 1;
    		else if (k > r[mid]) low = mid + 1;
    		else return mid + 1;
    	}
    	return 0;
    }
     
    int main()
    {
        
    	int n;
    	cin >> n;
    	int i, a[100];
    	for (i = 0; i < n; i ++)
    	{
        
    		cin >> a[i];
    	}
    	int k;
    	cin >> k;
    	cout << BinSearch(a, n, k) << endl;
    }

1.折半查找是一种二分搜索算法，它可以在有序数组中查找特定值。

**其基本思想是从数组的中间开始比较，如果当前值大于目标值，则在左侧继续查找；如果小于目标值，则在右侧继续查找；如果相等，则返回当前位置。**

2.折半查找也可以使用减治法进行实现。

**减治法是一种分而治之的算法思想，它将问题逐步缩小，直到可以很容易地解决问题。在折半查找中，减治法的基本思想是将当前数组的左半部分或右半部分递归地再进行折半查找，直到找到或者无法找到目标值。**

下面是使用减治法实现折半查找的 C++ 代码示例：

#include <iostream>
    
    using namespace std;
    
    int binarySearch(int arr[], int left, int right, int x) {
        if (right >= left) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == x)
                return mid;
            if (arr[mid] > x)
                return binarySearch(arr, left, mid - 1, x);
            return binarySearch(arr, mid + 1, right, x);
        }
        return -1;
    }
    
    int main() {
        int arr[] = { 2, 3, 4, 10, 40 };
        int n = sizeof(arr) / sizeof(arr[0]);
        int x = 10;
        int result = binarySearch(arr, 0, n - 1, x);
        if (result == -1)
            cout << "Element is not present in array";
        else
            cout << "Element is present at index " << result;
        return 0;
    }

在这个代码示例中，我们使用了递归调用实现了折半查找的减治法实现。

[c29e4aa36381412e8059548da65798d5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/742cf6ebe88b4257ac84dd599c5b81a2.png
[f08af72824b040638438142821c92f49.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/815e398b0ec747ab80794cd45ed3a46d.png