Binary search [Java]
Approach\nSort the nums, given the divisor , find an index that is equals or greater than divisor, then loop through the numbers starting from the index.\n\n# C
# Approach\nSort the nums, given the divisor , find an index that is equals or greater than divisor, then loop through the numbers starting from the index.\n\n# Complexity\n- Time complexity:\n$$O(DlogN)$$\n\n- Space complexity:\n$$O(1)$$\n\n# Code\n```\nclass Solution {\n    private int binarySearch(int[] nums, int target) {\n        int i = 0;\n        int j = nums.length;\n        while(i < j) {\n            int mid = i + (j - i) / 2;\n            if(nums[mid] < target) {\n                i = mid + 1;\n            } else {\n                j = mid;\n            }\n        }\n        return i;\n    }\n    public int maxDivScore(int[] nums, int[] divisors) {\n        Arrays.sort(nums);\n        int max = 0;\n        int res = divisors[0];\n        for(int d : divisors) {\n            int score = 0;\n            for(int i = binarySearch(nums, d); i < nums.length; ++i) {\n                if( nums[i] % d == 0) {\n                    ++score;\n                }\n            }\n            if(score > max) {\n                max = score;\n                res = d;\n            } else if (score == max) {\n                res = Math.min(res, d);\n            }\n        }\n        return res;\n    }\n}\n```\n\n### [Optimize] Sort both nums and divisors, and limit the lower bound.\n\n```java\nclass Solution {\n    private int binarySearch(int[] nums, int target, int lo) {\n        int hi = nums.length;\n        while(lo < hi) {\n            int mid = lo + (hi - lo) / 2;\n            if(nums[mid] < target) {\n                lo = mid + 1;\n            } else {\n                hi = mid;\n            }\n        }\n        return lo;\n    }\n\n    public int maxDivScore(int[] nums, int[] divisors) {\n        Arrays.sort(nums);\n        Arrays.sort(divisors);\n        int max = 0;\n        int res = divisors[0];\n        int lo = 0;\n        for(int d : divisors) {\n            int score = 0;\n            lo = binarySearch(nums, d, lo);\n            if(lo >= nums.length) {\n                break;\n            }\n            for(int i = lo; i < nums.length; ++i) {\n                if( nums[i] % d == 0) {\n                    ++score;\n                }\n            }\n            if(score > max) {\n                max = score;\n                res = d;\n            } else if (score == max) {\n                res = Math.min(res, d);\n            }\n        }\n        return res;\n    }\n}\n```
['Java']