fork download
copy 
  1. import java.util.Arrays;
  2. /**
  3.  * Find K closest elements to a given number in a sorted array
  4.  * @author PRATEEK
  5.  */
  6. class KClosestElements {
  7.  
  8.  
  9. 	public static void main(String[] args) {
  10. 		int[] arr= {1,2,3,4,5,6,7,8,9,10,11};
  11. 		int index=binarySearch(arr, 7, 0, arr.length);
  12. 		int k=4;
  13. 		if(index!=-1)
  14. 		{
  15. 			int[] result=KClosestElements(arr,index,k);
  16. 		}
  17. 	}
  18.  
  19. 	private static int binarySearch(int[]arr,int num,int low,int high) {
  20. 		while(low<=high)
  21. 		{
  22. 			int mid=(low+high)/2;
  23. 			if(arr[mid]==num)			return mid;
  24. 			else if(arr[mid] < num)		low=mid+1;
  25. 			else if (arr[mid] > num)	high=mid-1;
  26. 		}
  27. 		return -1;
  28. 	}
  29.  
  30. 	public static int[] KClosestElements(int[] arr, int index, int k){
  31. 		int left = index -1;
  32. 		int right = index +1;
  33. 		int[] result = new int[k];
  34.  
  35. 		while(right - left -2 < k )
  36. 		{
  37. 			if(arr[right] - arr[index] > arr[index]- arr[left])
  38. 			{
  39. 				if(left>0)
  40. 					result[right - left - 2] = arr[left--];
  41. 				else 
  42. 					result[right - left - 2]=arr[right++];
  43. 			}
  44. 			else
  45. 			{
  46. 				if(right < arr.length)
  47. 					result[right - left - 2]=arr[right++];
  48. 				else
  49. 					result[right - left - 2] = arr[left--];
  50. 			}
  51.  
  52. 			//result[right - left] = arr[right] - arr[index] > arr[index]- arr[left] ?  if(left>0){arr[left--]} : arr[right++] ;
  53. 		}
  54. 		System.out.println(Arrays.toString(result));
  55.  
  56. 		return result;
  57. 	}
  58. }
  59.  
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[8, 6, 9, 5]
https://ideone.com/C97KkX
K Closest Elements in a Sorted array
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!