三分查找算法

爱被打了一巴掌 2023-02-20 04:56 23阅读 0赞

# 原理 #

三分法的原理也很简单，和二分法几乎一模一样，只不过我们分隔区间的时候，不是将区间一分为二，而是一分为三。之后，我们同样通过缩小区间的方法来确定要查找的值所在。

但是：既然分成两份就能解决问题，我们为什么要分成三份呢？

在回答这个问题之前，我们先来看另一个问题。在数学上，二分法究竟解决了一个什么问题？

还记得二分法使用的前提吗？数组必须是**有序**的，所以二分法其实解决的是**单调函数**的求解问题。只要数组是有序的，根据函数的定义就可以看做是一个将数组下标映射到数组取值的函数。显然，这是一个单调函数，我们通过二分法查找其中的一个元素v，本质是查找

![在这里插入图片描述][2020062314370286.png]  
的解。

所以，二分法使用的场景是单调函数，也就是一次函数。那如果我要搜索二次函数的最小值，用二分法可行吗？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]  
显然不可行，因为我们在取完mid之后， 并不知道答案可能出现在左右哪个区间。

这个时候就需要三分法出场了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]  
三分法会将区间分成三份，这个我们都已经知道了。分成三份，自然需要两个端点。这两个端点各有一个值，我们分别叫做m1和m2。我们要求的是函数的最小值，所以我们要想极值逼近。

但是我们有两个中间点，该怎么逼近呢？

我们直接根据函数图像来分析，根据上图我们可以看出来，m1和m2的函数值和它们距离极值点的远近是有关系的。离极值点越近，函数值越小(也有可能越大，视函数而定)。在上图当中，  
![在这里插入图片描述][20200623144007972.png]  
，所以m2离极值点更近。我们要缩小区间范围，逼近极值点，所以我们应该让  
![在这里插入图片描述][20200623144206287.png]  
这里有一点小问题，我们怎么确定极值点在m2和m1中间呢？万一在m2的右侧该怎么办呢？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 2]  
我们画出图像来看，这种情况其实并没有区别，我们只会抛弃区间

![在这里插入图片描述][20200623144234832.png]  
，并不会影响极值点。

会不会极值点在m1左侧呢？这是不可能的，因为如果极值点在m1左侧，那么m2距离极值点一定比m1远，这种情况下m2处的函数值是不可能小于m1的。

也就是说，三分法的精髓在于，**每次通过比较两个值的大小，缩小三分之一的区间。直到最后区间的范围小于我们设置的阈值为止**

# 过程 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 3]

*  使用两个点将之分为三段：

>  *  midl = left + (right - left)/3;
>  *  midr= right - (right - left)/3;

*  如果midl比midr更加靠近最值点，我们就令 right = midr- 1; 【舍弃远离的那一段】
 *  如果midr比midl更加靠近罪之颠，令left = midl + 1； 【舍弃远离的那一段】

**假如是取最大值，则midr和midl中谁大谁更靠近最终的结果，于是最终选择的区间一定要包含较大者；同样取最小值也是这样的**，也就是：

*  若f(m1) < f(m2)，说明极值点位于\[m1, r\]区间内，可以不必再考虑\[l, m1\]区间；
 *  若f(m1) > f(m2)，说明极值点位于\[l, m2\]区间内，可以不必再考虑\[m2, r\]区间

这样，每一轮迭代都会把查找范围限制在原来的2/3，直到最终逼近极值点，即l和r之间的差值接近无穷小。容易推导出三分查找的时间复杂度为：

T(n) = T(2n / 3) + 1 = O(log3n)

# 代码实现 #

public class TreeNode {
        
        // 数组中没有重复的元素
        private static int trisection_search(int[] arr){
        
            if (arr == null){
        
                return -1;
            }
    
            int left = 0;
            int right = arr.length;
            while (left < right ){
        
                int midl = left + (right - left)/3;
                int midr = right - (right - left)/3;
    
    
                if (arr[midl] > arr[midr]){
        
                    right = midr - 1;
                }else{
        
                    left = midl + 1;
                }
    
            }
    
    
            return left;
        }
    
    
    
        public static void main(String[] args) {
        
            int arr[] = {
        1,2,5,7,11,14,16,17,20,22,25,28,30,33,35,38,40,42,46,50,53,57,58,60, 55, 44, 33, 22, 11 , 10, 7, 6, 5, 1};
    
            int index= trisection_search(arr);
            if (index == -1){
        
                System.out.println("找不到");
            }else{
        
                System.out.println("索引" + index + "值为" + arr[index]);
            }
        }
    }

当日，三分查找也可以再单调函数中找最值

static bool Find(int[] sortedArray, int number)
    {
        
     if (sortedArray.Length == 0)
      return false;
     int start = 0;
     int end = sortedArray.Length - 1;
     while (end >= start)
     {
        
      int firstMiddle = (end - start) / 3 + start;
      int secondMiddle = end - (end - start) / 3;
      if (sortedArray[firstMiddle] > number)
       end = firstMiddle - 1;
      else if (sortedArray[secondMiddle] < number)
       start = secondMiddle + 1;
      else if (sortedArray[firstMiddle] != number && sortedArray[secondMiddle] != number)
      {
        
       end = secondMiddle - 1;
       start = firstMiddle + 1;
      }
      else
       return true;
     }
     return false;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 4]

[2020062314370286.png]: https://img-blog.csdnimg.cn/2020062314370286.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200623143759520.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200623143826866.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200623144007972.png]: https://img-blog.csdnimg.cn/20200623144007972.png
[20200623144206287.png]: https://img-blog.csdnimg.cn/20200623144206287.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200623144219914.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200623144234832.png]: https://img-blog.csdnimg.cn/20200623144234832.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200623145804482.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2020062320562752.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70