Teaching Kids Programming – Using Binary Search to Find K-th Largest Number in Array

Teaching Kids Programming: Videos on Data Structures and Algorithms

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

Although this problem can be solved by many algorithms: sorting, priority queue etc, it would be also solved by using binary search algorithm.

Binary Search Algorithm to Find the Kth Largest Number in Array

If we define a function to count how many elements that are larger or equal to a target, we can do this in O(N) time. Then we can binary search the Kth largest number within the range of [min, max]. Please note that if there are equal or more than K numbers larger than current mid, we need to search in the upper half where we are trying to make mid higher so that the count will be smaller. Otherwise, we will search in the lower half.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def countHowManyLargerOrEqualThan(n):
            ans = 0
            for i in nums:
                if i >= n:
                    ans += 1
            return ans
        
        left, right = min(nums), max(nums)
        while left <= right:
            mid = (left + right) // 2
            x = countHowManyLargerOrEqualThan(mid)
            if x >= k:
                left = mid + 1
            else:
                right = mid - 1
        return right

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def countHowManyLargerOrEqualThan(n):
            ans = 0
            for i in nums:
                if i >= n:
                    ans += 1
            return ans
        
        left, right = min(nums), max(nums)
        while left <= right:
            mid = (left + right) // 2
            x = countHowManyLargerOrEqualThan(mid)
            if x >= k:
                left = mid + 1
            else:
                right = mid - 1
        return right

Binary Search takes O(LogN) and overall the above algorithm to find the Kth largest element will be O(NLogN) and space complexity is O(1) constant. Of course you could sort the array in O(NLogN) and find Kth largest immediately (if you are allow to modify the array)

1
2
3
4

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort()
        return nums[-k]

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort()
        return nums[-k]

–EOF (The Ultimate Computing & Technology Blog) —