can't we use binary search on K ?? need help || why this fails
i did binary search on value of k (0 to (maxelement-minelement)) \nif more elements r less than our current assumed k than high=k-1\nelse low=k+1\n\nANSWER:\nth
i did binary search on value of k (0 to (maxelement-minelement)) \nif more elements r less than our current assumed k than high=k-1\nelse low=k+1\n\nANSWER:\nthis fails because our function here is not monotonic in nature\ni thought maybe counting elements will be enough to steer in one direction but it doesn\'t gaurantee the solution in that case\n\n\n```\nclass Solution {\npublic:\n    vector<int> recoverArray(vector<int>& nums) {\n        unordered_map<int,vector<int>> ump;\n        int n=nums.size();\n        int low=nums[0],high=nums[0];\n        for(int i=0;i<n;++i){\n            ump[nums[i]].push_back(i);\n            low=min(low,nums[i]);\n            high=max(high,nums[i]);\n        }\n        vector<int> ans(n/2,0);\n        \n        high=(high-low);\n        const int mini=low;\n        low=0;\n        \n        while(low<=high){\n            int k=low+((high-low)>>1);\n            vector<int> ans;\n            int count=n/2,lt=0,gt=0;\n            vector<int> index(n,0);\n            \n            for(int i=0;i<n;++i){\n                if(index[i]!=0)continue;\n                if(nums[i]>k+mini)gt++;\n                else lt++;\n                \n                if(ump.find(2*k+nums[i])!=ump.end()){\n                    bool s=0;\n                    for(int go:ump[2*k+nums[i]]){\n                        if(index[go]==0){\n                            s=1;\n                            index[go]+=1;\n                            break;\n                        }\n                    }\n                    if(s){\n                        ans.push_back(nums[i]+k);\n                        index[i]+=1;\n                        count--;\n                    }\n                }\n                \n            }\n            \n            cout<<k<<" ";\n            if(count==0){\n                return ans;\n            }else{\n                if(lt>=gt){\n                    high=k-1;\n                }else{\n                    low=k+1;\n                }\n            }\n            \n        }\n        \n        return nums;\n        \n    }\n};\n```
[]