✅Detailed Explanation || Binary Search || C++ , java
Read the whole post and solution code to get clear understanding.\n\nQuestion explanation :\nAlice has array nums with n elements which is not given us. He choo
*Read the whole post and solution code to get clear understanding.*\n\n**Question explanation :**\nAlice has array nums with n elements which is not given us. He chooses a **positive** integer **k** and created two new array of **same size** from the array he has\n1.) **lower array**\n2.) **higher array**\n\nfor each **i** to n:\n\nlower[i]  = **nums[i] - k**; \nhigher[i] = **nums[i] + k**;\n\n* we neither given nums nor lower and higher array but \n* we are given an array of size 2n which is **combination** of elements of array **lower** and **higher**\n* here elements are arranged **randomly** we not know which element belongs which array (lower or higher)\n* we have to create an array Alice has.\n\n**Solution Explaination:**\n\n* For any valid k value we take lower[i] element and search for their higher[i]  in nums\n*  such that lower[i] =  higher[i] + 2*k   explain below\n\nI would like to explain you with example \n\n   ```nums =  [11, 6, 3, 4, 8, 7, 8, 7, 9, 8, 9, 10, 10, 2, 1, 9] n = 16```\n\n* since k is subtracting and adding from each nums[i] to create lower and higher array respectively.\n* k is same for all so the smallest value belongs to the lower array.\n\nfirstly we sort the given array so it becomes\n\t\t\t```[1, 2, 3, 4, 6, 7, 7, 8, 8, 8, 9, 9, 9, 10, 10, 11]```\n\n***Little Maths Equations***\n```\t\t\t    \t\t\t\nlower[i] =   nums[i] - k\t\t (given in ques)                 \nnums[i]  =  lower[i] + k        ....1)       \t   \n \nhigher[i] =  nums[i]  + k        (given in ques)\nnums[i]  =   higher[i] - k      ....2)   \n\nusing 1 and  2\n  lower[i] + k     =  higher[i] - k\n  lower[i] + 2k    =  higher[i]   \n  \n``` \n ***higher[i] = lower[i] + 2k***   // so we  can say that for every higher **there is a match** in lower or vice versa.\n  \n we use above equation to find the match with every lower\n\n```\nalso for getting k value\nk = (higher[i] - lower[i])/2  (using above equation)\n```\n\n**Instead** of trying for every possible value we only need to try with **smallest** element to find a **valid k** value. (since **at** **least** one ans possible)\n\nSo lets **dry** run the above example \n     ```nums[] =  [1, 2, 3, 4, 6, 7, 7, 8, 8, 8, 9, 9, 9, 10, 10, 11]```\n\n **smallest**  = nums[0] = 1\n ``` \n   k = (nums[i] - smallest)/2\n```\n  for **checking** valid k \n ```        we check  if k>0 && smallest + 2*k == nums[i] ```\n\nfrom **each** index  i = 1 to n in nums:\n```\ni= 1:\n\n\t\t\t nums[i] = 2\n\t\t\t k = (2 - 1)/2;\n\t\t\t k = 0 (not valid); \n\n\ni = 2:\n\n\t\t\t nums[i] = 3\n\t\t\t k = (3-1)/2;\n\t\t\t k = 1 (valid)\n```\t\t \n **Now we try to find match of every lower with higher**\n\nfor **each** i = 0 to n in nums \n\n\t\ttarget = nums[i] + 2*k;  // we search  target value in nums (since for every lower there is a match in higher if we find valid k)\n\t\tans =  [] \n\n\ti= 0:\n\t\tnums[i] =1\n\n\t\t\ttarget =  1 + 2*1 = 3 (present in nums[2] mark as visited)\n\t\t\tpush (nums[i] + k) in ans array\n\n\t\t\tnums[i] + k = 2\n\t\t\tans = [2]\n\n\ti= 1: \n\t\tnums[i] =2\n\n\t\t\ttarget =  2 + 2*1 = 4 (present in nums[3] mark as visited)\n\t\t\tpush (nums[i] + k) in ans array\n\n\t\t\tnums[i] + k =3\n\t\t\tans = [2,3]\n\n\ti= 2:\n\t\t   nums[i] = 3  (already visited (matched with index 0) so  skip it\n\n\ti= 3:\n\t\t\tnums[i] = 4 (already visited (matched with index 1) so  skip it\n\n\ti= 4:\n\t\t\tnums[i] = 6\n\n\t\t\ttarget =  6 + 2*1 = 8 (present in nums[7] mark as visited)\n\t\t\tNote : here we find multiple 8 but we start from the leftmost.\n\n\t\t\tpush (nums[i] + k ) in ans array\n\n\t\t\tnums[i] + k = 7;\n\t\t\tans = [2,3,7]\n\n\ti= 5:\n\t\tnums[i] = 7\n\n\t\t\ttarget =  7 + 2*1 = 9 (present in nums[10] mark as visited)\n\t\t\tagain we find multiple value equals to target but start from the leftmost\n\n\t\t\tpush (nums[i] + k) in ans array\n\n\t\t\tnums[i] + k = 8\n\t\t\tans = [2,3,7,8]\n\n\ti= 6:\n\t\tnums[i] = 7\n\n\t\t\ttarget =  7 + 2*1 = 9 (present in nums[11] mark as visited)\n\t\t\tpush (nums[i] + k) in ans array\n\n\t\t\tnums[i] + k = 8\n\t\t\tans = [2,3,7,8,8]\n\n\ti=7:\n\t\t\tnums[i] = 8 (already visited (matched with index 4) so  skip it\n\n\n\ti=8:\n\t\tnums[i] = 8\n\n\t\t\ttarget =  8 + 2*1 = 10 (present in nums[13] mark as visited)\n\t\t\tpush (nums[i] + k) in ans array\n\n\t\t\tnums[i] + k = 9\n\t\t\tans = [2,3,7,8,8,9]\n\n\ti=9:\n\t\tnums[i] = 8\n\n\t\t\ttarget =  8 + 2*1 = 10 (present in nums[14] mark as visited)\n\t\t\tpush (nums[i] + k which 9) in ans array\n\n\t\t\tnums[i] + k = 9\n\t\t\tans = [2,3,7,8,8,9,9]\n\n\ti=10:\n\t\t\tnums[i] = 9 (already visited (matched with index 5) so  skip it\n\n\ti=11:\n\t\t\tnums[i] = 9 (already visited (matched with index 6) so  skip it\n\n\ti=12:\n\t\tnums[i] = 9\n\n\t\t\ttarget =  9 + 2*1 = 11 (present in nums[15] mark as visited)\n\t\t\tpush (nums[i] + k) in ans array\n\n\t\t\tnums[i] + k = 10\n\t\t\tans = [2,3,7,8,8,9,9,10]\n\n\n\ti = 13,14 15   \n\t\t\t\t\talready visited so skip it\n\n\t\tans = [2,3,7,8,8,9,9,10] // bingo  our ans array size equals to n/2  hence we found a valid array.\n\t\t\n\n***Solution Code :-***\n\n```\nclass Solution\n{\npublic:\n    int search(vector<int> &nums, vector<bool> visit, int low, int high, int target)\n    {\n        int index = -1;\n\n        while (low <= high)\n        {\n\n            int mid = (low + high) / 2;\n\n            if (nums[mid] == target)\n            {\n                if (visit[mid])\n                {\n                    low = mid + 1;\n                }\n                else\n                {\n                    index = mid;  \n                    high = mid - 1; \n                }\n\n                continue;\n            }\n\n            if (nums[mid] > target)\n                high = mid - 1;\n            else\n                low = mid + 1;\n        }\n\n        return index;\n    }\n\n    vector<int> recoverArray(vector<int> &nums)\n    {\n\n        int n = nums.size();\n        sort(nums.begin(), nums.end());\n\n        int smallest = nums[0];\n\n        for (int i = 1; i < n; i++)\n        {\n\n            int k = (nums[i] - smallest) / 2; \n            if (k <= 0 || smallest + 2 * k != nums[i]) \n                continue;\n\n            vector<bool> visit(n);\n            vector<int> ans;\n\n            for (int j = 0; j < n; j++)\n            {\n\n                if (visit[j]) \n                    continue;\n\n                int target = nums[j] + 2 * k;\n\n                int index = search(nums, visit, j + 1, n - 1, target);\n\n                if (index == -1) \n                    break;\n\n                visit[index] = true; \n                ans.push_back(nums[j] + k); \n            }\n\n            if (ans.size() == n / 2)\n                return ans;\n        }\n\n        return {};\n    }\n};\n\n```\n\n```\n\nclass Solution {\n    \n int search(int nums[],boolean visit[] ,int low,int high,int target){\n     int index  = -1;\n     \n      while(low <= high){\n          int mid =  (low + high)/2;\n            if(nums[mid]==target){\n                if(visit[mid]){\n                   low = mid +1;\n                 }\n                 else{\n                      index = mid;    \n                      high = mid-1; \n                    }\n                   continue;\n                }\n\n                if(nums[mid] > target)\n                   high = mid-1;\n                else\n                   low = mid +1;\n     }\n      return index;\n}\n    \n    public int[] recoverArray(int[]nums) {\n        \n       int n  = nums.length;\n       Arrays.sort(nums);\n       \n       int smallest = nums[0];\n       \n         for(int i =1;i<n;i++){\n               \n              int k = (nums[i] - smallest)/2; \n               \n               if(k<=0 || smallest + 2*k != nums[i]) \n                     continue;\n             \n                       boolean visit[] = new boolean[n];\n                       int ans[] = new int[n/2];        \n                       int cnt = 0;\n                       for(int j=0;j<n;j++){\n                       \n                           if(visit[j]) \n                              continue;\n                       \n                           int target = nums[j] + 2*k; \n                           int index = search(nums,visit,j+1,n-1, target);                  \n                           if(index==-1)\n                               break;\n                        \n                           visit[index] = true; \n                           ans[cnt++] = nums[j] + k; \n            \n                       }\n                         if(cnt==n/2) \n                             return ans;\n         }\n       \n       return new int[0];\n     }\n}\n\n```\n\n\n***Time Complexity : - O(n^2 logn)\n Space Complexity :- O(n)  (for maintaining visited array)***\n\n ***If you Like this post please do upvote so other people can also take benefit of this.\n any doubt welcome in comment section.***\n
['Binary Tree']