java binary search
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int[] resultArray(int[] nums) {\n        \n        List<Integer> list1 = new ArrayList<Integer>();\n        List<Integer> sortedList1 = new ArrayList<Integer>();\n        \n        List<Integer> list2 = new ArrayList<Integer>();\n        List<Integer> sortedList2 = new ArrayList<Integer>();\n\n        list1.add(nums[0]);\n        sortedList1.add(nums[0]);\n\n        list2.add(nums[1]);\n        sortedList2.add(nums[1]);\n\n        for(int i = 2; i < nums.length; i++) {\n            int idx1 = binarySearchUpper(sortedList1, nums[i]);\n            int idx2 = binarySearchUpper(sortedList2, nums[i]);\n\n            if ( list1.size()-idx1 > list2.size()-idx2) {\n                list1.add(nums[i]);\n                sortedList1.add(idx1, nums[i]);\n            } else if (list1.size()-idx1 < list2.size()-idx2 ) {\n                list2.add(nums[i]);\n                sortedList2.add(idx2, nums[i]);\n            } else{\n                if ( sortedList1.size() <=  sortedList2.size()) {\n                    list1.add(nums[i]);\n                    sortedList1.add(idx1, nums[i]);\n                } else{\n                    list2.add(nums[i]);\n                    sortedList2.add(idx2, nums[i]);\n                }\n            }\n        }\n\n        int result[] = new int[nums.length];\n        int ridx = 0;\n        for(int i = 0; i < list1.size(); i++) {\n            result[ridx++] = list1.get(i);\n        }\n\n        for(int i = 0; i < list2.size(); i++) {\n            result[ridx++] = list2.get(i);\n        }\n\n        return result;\n    }\n\n    private int binarySearchUpper(List<Integer> list, int target) {\n        int start = 0;\n        int end = list.size();\n        int mid;\n\n        while(start < end) {\n            mid = (start+end)/2;\n\n            if ( list.get(mid) > target) {\n                end =mid;\n            } else{\n                start = mid+1;\n            }\n        }\n\n        return end;\n    }\n}\n```
['Binary Search', 'Java']