[Java/C++] Very simple binary search solution


  • 13

    The idea is to find the first number which is equal to or greater than x in arr. Then, we determine the indices of the start and the end of a subarray in arr, where the subarray is our result. The time complexity is O(logn + k).

    In the following code, arr[index] is the first number which is euqal to or geater than x (if all numbers are less than x, index is arr.size()), and the result is arr[i+1, i+2, ... j].

    Java version:

        public List<Integer> findClosestElements(List<Integer> arr, int k, int x) {
            int index = Collections.binarySearch(arr, x);
            if(index < 0) index = -(index + 1);
            int i = index - 1, j = index;                                    
            while(k-- > 0){
                if(i<0 || (j<arr.size() && Math.abs(arr.get(i) - x) > Math.abs(arr.get(j) - x) ))j++;
                else i--;
            }
            return arr.subList(i+1, j);
        }
    

    C++ version:

        vector<int> findClosestElements(vector<int>& arr, int k, int x) {
            int index = std::lower_bound(arr.begin(), arr.end(), x) - arr.begin();
            int i = index - 1, j = index;                                    
            while(k--) (i<0 || (j<arr.size() && abs(arr[i] - x) > abs(arr[j] - x) ))? j++: i--;
            return vector<int>(arr.begin() + i + 1, arr.begin() + j );
        }
    

  • 0
    G

    Soooo nice piece of code!


  • 1
    B

    @Hao-Cai Could you kindly elaborate the intuition behind initializing i as index-1? I initialized both of my pointers left and right equal to index and then proceeded towards expanding them out words. However, this resulted in incorrect results.


  • 0

    @BatCoder Thanks for your question! You can consider the case of k=1, the only number of the result might be arr[index-1], not arr[index].


  • 0
    B

    So smart and so nice coding skill


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.