Check whether a given array is a k sorted array or not | function to find index of element ' x ' in sorted ' arr ' uses binary search technique ; function to check whether the given array is a ' k ' sorted array or not ; auxiliary array ' aux ' ; copy elements of ' arr ' to ' aux ' ; sort ' aux ' ; for every element of ' arr ' at index ' i ' , find its index ' j ' in ' aux ' ; index of arr [ i ] in sorted array ' aux ' ; if abs ( i - j ) > k , then that element is not at - most k distance away from its target position . Thus , ' arr ' is not a k sorted array ; ' arr ' is a k sorted array ; Driver program to test above
function binarySearch ( arr , low , high , x ) { while ( low <= high ) { var mid = parseInt ( ( low + high ) / 2 ) ; if ( arr [ mid ] == x ) return mid ; else if ( arr [ mid ] > x ) high = mid - 1 ; else low = mid + 1 ; } } function isKSortedArray ( arr , n , k ) { var aux = Array ( n ) ; for ( var i = 0 ; i < n ; i ++ ) aux [ i ] = arr [ i ] ; aux . sort ( ( a , b ) => a - b ) for ( var i = 0 ; i < n ; i ++ ) { var j = binarySearch ( aux , 0 , n - 1 , arr [ i ] ) ; if ( Math . abs ( i - j ) > k ) return " " ; } return " " ; } var arr = [ 3 , 2 , 1 , 5 , 6 , 4 ] ; var n = arr . length ; var k = 2 ; document . write ( " " + isKSortedArray ( arr , n , k ) ) ;