三分找极点

三分搜索概念

三分搜索tips

找极大值的时候若左中点比右中点更靠近极大值，right取右边中点；否则left取左边中点（找极小值相反）
找极大值坐标的时候，while循环的判断条件可以设为right-left>4，留出空挡就可以不用判断边界了

三分搜索模板

--三分找极点值，二维--
const double EPS = 1e-10;
double cal(double x)
{
    // f(x) = -(x-3)^2 + 2;  
    return (x-3.0)*(x-3.0) + 2;
}

double threeSearch(double low, double high)
{
    while(high-low>EPS)
    {
        double mid = low + (high-low)/2;
        double midmid = mid+(high-mid)/2;
        if(cal(mid)>cal(midmid)) //找极大值用>, 找极小值用<
            high = midmid;
        else
            low = mid;
    }
    return low;
}

--三分找极值点坐标--
int threeSearch(vector<int> nums)
{
    int left = 0, right = nums.size()-1;
    //trick：留出空档来就不用判断边界条件了
    while(right-left>4){
        int mid = left + (right-left)/2;
        int midmid = mid+(right-mid)/2;
        if(nums[mid]>nums[midmid]) //极大用“>”，极小用“<”
            right = midmid-1;
        else
            left = mid+1;
    }
    int pos = left;//pos为最终目标
    for(int i=left;i<right;i++)
    {
        if(nums[i]<=nums[i+1]) //极大用"<="，极小用">="
            pos = i+1;
        else
            break;
    }
    return pos;
}

##实战

题目

一个先升序后降序的数组中判断一个数是否存在

解法

先三分找极点，然后二分判断是否存在

#include<iostream>
#include <vector>
using namespace std;

//三分找极值点坐标，一维
int threeSearch(vector<int> nums)
{
    int left = 0, right = nums.size()-1;
    //trick：留出空档来就不用判断边界条件了
    while(right-left>4){
        int mid = left + (right-left)/2;
        int midmid = mid+(right-mid)/2;
        if(nums[mid]>nums[midmid]) //极大用“>”，极小用“<”
            right = midmid-1;
        else
            left = mid+1;
    }
    int pos = left;//pos为最终目标
    for(int i=left;i<right;i++)
    {
        if(nums[i]<=nums[i+1]) //极大用"<="，极小用">="
            pos = i+1;
        else
            break;
    }
    return pos;
}

bool inNums(vector<int>nums, int key)
{
    int index = threeSearch(nums);
    int left = 0, right = index;
    //在上升序列中找是否存在
    while(left<=right)
    {
        int mid = left + (right-left)/2;
        if(nums[mid]>key)
            right = mid-1;
        else if(nums[mid]<key)
            left = mid+1;
        else
            return true;
    }
    if(key>nums[index])
        return false;
    //在下降序列中找是否存在
    left = index+1, right = nums.size()-1;
    while(left<=right)
    {
        int mid = left + (right-left)/2;
        if(nums[mid]<key)
            right = mid-1;
        else if(nums[mid]>key)
            left = mid+1;
        else
            return true;
    }
    return false;
}
int main()
{
    int temp[] = {1,2,3,3,3,4,4,3,3,2,1};
    vector<int> test(temp, temp+sizeof(temp)/sizeof(int));
    cout<<inNums(test, 1)<<endl;
    return 0;
}