# Binary Search Answer, O(N * constant)

• The idea is to search for the answer, and check whether the given answer is at Kth maximum position.

Given the range of all possible value, we can narrow down the range of final results by using binary search. For example, the range of all possible value is 0 .. 100,

1. we first try whether mid-value (e.g. 50) is the Kth maximum position.
2. To verify, we scan the array and count how many elements are greater than or equal to 50.
3. if the count > K, then the real answer should be greater than mid-value (e.g. 50), we search answer in 51 ... 100; otherwise, the real answer should be less than mid-value, we search answer in 0..50

Every time, It takes O(N) to verify the position of the current result.
It will take O(log C) times to do the verification, where C is the range of the possible value, which we can treat it as O(1)

``````# @param {Integer[]} nums
# @param {Integer} k
# @return {Integer}
def find_kth_largest(nums, k)
min, max = nums[0], nums[0]
nums.each {|x|
min = [min, x].min
max = [max, x].max
}
while min <= max
mid = (min + max) / 2
count = 0;
nums.each{|x| count += 1 if x >= mid}
if count >= k
min = mid + 1
else
max = mid - 1
end
end
return max
end``````

• A rather "bold" move to treat the range as O(1). But whatever, I like the idea, and I like Ruby :-) Here's a shorter version, though:

``````def find_kth_largest(nums, k)
min, max = nums.minmax
while min <= max
mid = (min + max) / 2
if nums.count{|x| x >= mid} >= k
min = mid + 1
else
max = mid - 1
end
end
max
end
``````

• wow! Thanks Stefan, your code is really elegant!!

• Ruby is such a treasure trove, you just need to use it all :-). I just came across each_cons while solving another problem. Mind-blowing. I'm a Ruby beginner and I'm already loving it.

• "you just need to use it all", lol. What a newb I was :-). I just did this again, now in one line by using `bsearch`.

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