题解 | #动物牛的数学问题# 二分查找解法

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型vector
     */
    struct node{
        int i;
        int num;
        bool operator <(const node& b)const
        {
            return num<b.num;
        }
        node(int index,int n):i(index),num(n)
        {
            
        }
    };
    vector<int> twoSum(vector<int>& nums, int target) {
        // write code here
        //my_nums=nums;
        vector<int> ans;
        for(int i=0;i<nums.size();i++)
        {
            my_nodes.push_back(node(i,nums[i]));
        }
        sort(my_nodes.begin(),my_nodes.end());
        for(int i=0;i<my_nodes.size()-1;i++)
        {
            int res=half_find(my_nodes,i+1, my_nodes.size(), target-my_nodes[i].num);
            if(res!=-1)
            {
                ans.push_back(my_nodes[i].i);
                ans.push_back(my_nodes[res].i);
                return ans;
            }
        }
        return ans;
    }
    
    int half_find(vector<node>& nodes,int l,int r,int target)
    {
        int mid=(l+r)/2;

        if(l>r)
        {
            return -1;
        }
        
        if(nodes[mid].num==target)
        {
            return mid;
        }
        else if(nodes[mid].num>target)
        {
            return half_find(nodes,l, mid-1, target);
        }
        else
        {
            return half_find(nodes,mid+1, r, target);
        }
        return -1;
    }
private:
    vector<node> my_nodes;
};