K largest elements in an array using Binary Search
The idea is to find the Kth largest element of the array and then print all the elements which are greater than or equal to Kth largest Element. The Kth largest element can be found using binary search by defining a search range based on the minimum and maximum values in the input array. In each iteration of binary search, count the larger than the midpoint and update the search range accordingly. This process continues until the range collapses to a single element, which is the kth largest element.
Follow the given steps to solve the problem:
- Initialize low and high to minimum and maximum element of the array denoting the range within which the answer lies.
- Apply Binary Search on this range.
- If the selected element by calculating mid has less than K elements lesser to it then increase the number that is low = mid + 1.
- Otherwise, Decrement the high pointer, i.e high = mid.
- The Binary Search will terminate when only one element remains in the answer space that would be the Kth largest element.
- Print all the elements which are greater than or equal to Kth largest element.
Below is the implementation of above approach:
// C++ code to implement the binary search approach
#include <algorithm>
#include <climits>
#include <iostream>
using namespace std;
// Function to find the Kth largest element in the array
// using binary search
int findKthLargest(int arr[], int n, int k)
{
int low = INT_MAX, high = INT_MIN;
// Find the minimum and maximum elements in the array
for (int i = 0; i < n; i++) {
low = min(low, arr[i]);
high = max(high, arr[i]);
}
// Perform binary search on the range of elements
// between low and high
while (low <= high) {
int mid = low + (high - low) / 2;
int count = 0;
// Count the number of elements greater than mid in
// the array
for (int i = 0; i < n; i++) {
if (arr[i] > mid) {
count++;
}
}
// If there are at least K elements greater than
// mid, search the right half
if (count >= k) {
low = mid + 1;
}
// Otherwise, search the left half
else {
high = mid - 1;
}
}
// Return the Kth largest element
return high;
}
// Function to print the K largest elements in the array
void printKLargest(int arr[], int n, int k)
{
// Find the Kth largest element
int kthLargest = findKthLargest(arr, n, k);
// Print the K largest elements in decreasing order
for (int i = 0; i < n; i++) {
if (arr[i] >= kthLargest) {
cout << arr[i] << " ";
}
}
cout << endl;
}
// Driver code
int main()
{
int arr[] = { 12, 5, 787, 1, 23 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout << "K largest elements: ";
printKLargest(arr, n, k);
return 0;
}
// This code is contributed by Veerendra_Singh_Rajpoot
import java.io.*;
import java.util.*;
public class GFG {
public static int findKthLargest(int[] arr, int n,
int k)
{
int low = Integer.MAX_VALUE,
high = Integer.MIN_VALUE;
// Find the minimum and maximum elements in the
// array
for (int i : arr) {
low = Math.min(low, i);
high = Math.max(high, i);
}
// Perform binary search on the range of elements
// between low and high
while (low <= high) {
int mid = low + (high - low) / 2;
int count = 0;
// Count the number of elements greater than mid
// in the array
for (int i : arr) {
if (i > mid) {
count++;
}
}
// If there are at least K elements greater than
// mid, search the right half
if (count >= k) {
low = mid + 1;
}
// Otherwise, search the left half
else {
high = mid - 1;
}
}
// Return the Kth largest element
return high;
}
public static void printKLargest(int[] arr, int n,
int k)
{
// Find the Kth largest element
int kthLargest = findKthLargest(arr, n, k);
// Print the K largest elements in decreasing order
for (int i : arr) {
if (i >= kthLargest) {
System.out.print(" " + i);
}
}
}
public static void main(String[] args)
{
int[] arr = { 12, 5, 787, 1, 23 };
int n = arr.length;
int k = 2;
System.out.print("K largest elements:");
printKLargest(arr, n, k);
}
}
// This code is contributed by Rohit Singh
# Python code to implement the binary search approach
# Function to find the Kth largest element in the array using binary search
def findKthLargest(arr, n, k):
low = float('inf')
high = float('-inf')
# Find the minimum and maximum elements in the array
for i in range(n):
low = min(low, arr[i])
high = max(high, arr[i])
# Perform binary search on the range of elements between low and high
while low <= high:
mid = low + (high - low) // 2
count = 0
# Count the number of elements greater than mid in the array
for i in range(n):
if arr[i] > mid:
count += 1
# If there are at least K elements greater than mid, search the right half
if count >= k:
low = mid + 1
# Otherwise, search the left half
else:
high = mid - 1
# Return the Kth largest element
return high
# Function to print the K largest elements in the array
def printKLargest(arr, n, k):
# Find the Kth largest element
kthLargest = findKthLargest(arr, n, k)
# Print the K largest elements in decreasing order
print("K largest elements:", end=" ")
for i in range(n):
if arr[i] >= kthLargest:
print(arr[i], end=" ")
print()
# Driver code
if __name__ == '__main__':
arr = [12, 5, 787, 1, 23]
n = len(arr)
k = 2
printKLargest(arr, n, k)
# This code is contributed by Susobhan Akhuli
using System;
namespace KthLargestElement
{
class Program
{
static int FindKthLargest(int[] arr, int n, int k)
{
int low = int.MaxValue;
int high = int.MinValue;
// Find the minimum and maximum elements in the array
foreach (int num in arr)
{
low = Math.Min(low, num);
high = Math.Max(high, num);
}
// Perform binary search on the range of elements between low and high
while (low <= high)
{
int mid = low + (high - low) / 2;
int count = 0;
// Count the number of elements greater than mid in the array
foreach (int num in arr)
{
if (num > mid)
{
count++;
}
}
// If there are at least K elements greater than mid, search the right half
if (count >= k)
{
low = mid + 1;
}
// Otherwise, search the left half
else
{
high = mid - 1;
}
}
// Return the Kth largest element
return high;
}
static void PrintKLargest(int[] arr, int n, int k)
{
// Find the Kth largest element
int kthLargest = FindKthLargest(arr, n, k);
// Print the K largest elements in decreasing order
foreach (int num in arr)
{
if (num >= kthLargest)
{
Console.Write(num + " ");
}
}
Console.WriteLine();
}
static void Main(string[] args)
{
int[] arr = { 12, 5, 787, 1, 23 };
int n = arr.Length;
int k = 2;
Console.Write("K largest elements: ");
PrintKLargest(arr, n, k);
}
}
}
// Function to find the Kth largest element in the array using binary search
function findKthLargest(arr, k) {
let low = Number.POSITIVE_INFINITY;
let high = Number.NEGATIVE_INFINITY;
// Find the minimum and maximum elements in the array
for (let i = 0; i < arr.length; i++) {
low = Math.min(low, arr[i]);
high = Math.max(high, arr[i]);
}
// Perform binary search on the range of elements between low and high
while (low <= high) {
let mid = low + Math.floor((high - low) / 2);
let count = 0;
// Count the number of elements greater than mid in the array
for (let i = 0; i < arr.length; i++) {
if (arr[i] > mid) {
count++;
}
}
// If there are at least K elements greater than mid, search the right half
if (count >= k) {
low = mid + 1;
}
// Otherwise, search the left half
else {
high = mid - 1;
}
}
// Return the Kth largest element
return high;
}
// Function to print the K largest elements in the array
function printKLargest(arr, k) {
// Find the Kth largest element
const kthLargest = findKthLargest(arr, k);
// Print the K largest elements in decreasing order
process.stdout.write("K largest elements: ");
for (let i = 0; i < arr.length; i++) {
if (arr[i] >= kthLargest) {
process.stdout.write(arr[i] + " ");
}
}
console.log();
}
// Driver code
const arr = [12, 5, 787, 1, 23];
const k = 2;
printKLargest(arr, k);
Output
K largest elements: 787 23
Time complexity: O(n * log (mx-mn)), where mn be minimum and mx be maximum element of array.
Auxiliary Space: O(1)
Print K largest(or smallest) elements in an array
Given an array arr[] of size N, the task is to printing K largest elements in an array.
Note: Elements in output array can be in any order
Examples:
Input: [1, 23, 12, 9, 30, 2, 50], K = 3
Output: 50, 30, 23Input: [11, 5, 12, 9, 44, 17, 2], K = 2
Output: 44, 17