Answer to Question #275303 in C for Lucky

Question

Given an array arr[] sorted in ascending order of size N and an integer K.

Check if K is present in the array or not. (Use Binary Search)

Input: N = 5

K = 6

arr[] = {1,2,3,4,6}

Output: 1

Explanation: Since, 6 is present in the array at index 4 (0-based indexing),

output is 1

Answer 1

#include <bits / stdc++.h>
using namespace std;
int binarySearch(int arr[], int low, int high, int x)
{
	while (low <= high)
	{
		int mid = (low + high) / 2;
		
		if (arr[mid] == x)
			return mid;
		else if (arr[mid] > x)
			high = mid - 1;
		else
			low = mid + 1;
	}
}

string isKSortedArray(int arr[], int n, int k)
{
	int aux[n];
	for (int i = 0; i<n; i++)
		aux[i] = arr[i];
	sort(aux, aux + n);
	for (int i = 0; i<n; i++)
	{
		int j = binarySearch(aux, 0, n-1, arr[i]);
		
		if (abs(i - j) > k)
			return "No";
	}
	return "Yes";
}

int main()
{
	int arr[] = {3, 2, 1, 5, 6, 4};
	int n = sizeof(arr) / sizeof(arr[0]);
	int k = 2;
	cout << "Is it a k sorted array?: "
		<< isKSortedArray(arr, n, k);
	return 0;	
}