A step array is an array of integers where each element has a difference of at most k with its neighbor. Given a key x, we need to find the index value of x if multiple elements exist, and return the first occurrence of the key. 
Example 1:
Input : arr[ ] = {4, 5, 6, 7, 6}, K = 1 
        and X = 6
Output : 2
Explanation:
In an array arr 6 is present at index 2.
So, return 2.
Example 2:
Input : arr[ ] = {20 40 50}, K = 20 
        and X = 70
Output :  -1 
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function search() that takes an array (arr), sizeOfArray (n), an integer value X, another integer value K, and return an integer displaying the index of the element X in the array arr. If the element is not present in the array return -1. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ K ≤ 10^{2}
1 ≤ arr[i], X ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Complete search

Starter code: #User function Template for python3



def search (arr, n, x, k) : 

    #Complete the function



Solutions:
def search(arr, n, x, k):
	for i in range(n):
		if arr[i] == x:
			return i
	return -1


def search(arr, n, x, k):
	for i in range(len(arr)):
		i = 0
		while i < len(arr):
			if arr[i] == x:
				return i
			dif = abs(x - arr[i]) // k
			if dif == 0:
				dif += 1
			i += dif
		return -1


def search(arr, n, x, k):
	l = 0
	while l < n:
		if arr[l] == x:
			return l
		l = l + max(1, int(abs(arr[l] - x) / k))
	return -1


def search(arr, n, x, k):
	if x in arr:
		return arr.index(x)
	return -1


def search(arr, n, x, k):
	i = 0
	diff = 0
	while i < n:
		if arr[i] == x:
			return i
		else:
			diff = max(1, abs(arr[i] - x) // k)
		i = i + diff
	return -1


def search(arr, n, x, k):
	a = []
	for i in arr:
		if i == x:
			return arr.index(i)
	return '-1'


def search(arr, n, x, k):
	if x in arr:
		ind = arr.index(x)
		return ind
	else:
		return -1


def search(arr, n, x, k):
	for i in range(len(arr)):
		if arr[i] == x:
			return i
		i += max(1, int(abs(arr[i] - x) / k))
	return -1


def search(arr, n, x, k):
	i = 0
	while i < n:
		if arr[i] == x:
			return i
		if arr[i] + k < x:
			i += 2
		else:
			i += 1
	return -1


def search(arr, n, x, k):
	b = 0
	for i in range(len(arr)):
		a = arr.pop(0)
		if a == x:
			b = 1
			break
	return i if b == 1 else '-1'


def search(arr, n, x, k):
	thislist = []
	for i in range(0, n):
		if arr[i] == x:
			thislist.append(i)
			return thislist[0]
	return -1


def search(arr, n, x, k):
	i = 0
	while i < n:
		if arr[i] == x:
			return i
		ans = abs(arr[i] - x) // k
		ans = max(1, ans)
		i += ans
	return -1


def search(arr, n, x, k):
	i = 0
	while i < n:
		if arr[i] == x:
			return i
		else:
			steps = int(abs((arr[i] - x) / k))
			i += max(1, steps)
	return -1


def search(arr, n, x, k):
	for (idx, num) in enumerate(arr):
		if num == x:
			return idx
	return -1


def search(arr, n, x, k):
	idx = 0
	while idx < n:
		if arr[idx] == x:
			return idx
		diff = abs(arr[idx] - x)
		steps = diff // k
		if steps > 0:
			idx += steps
		else:
			idx += 1
	return -1


def search(arr, n, x, k):
	idx = 0
	while idx < n:
		if arr[idx] == x:
			return idx
		idx = idx + max(1, abs(arr[idx] - x) // k)
	return -1


def search(a, n, x, k):
	i = 0
	while i < n:
		current = a[i]
		if current == x:
			return i
		if current - k <= x <= current + k:
			i += 1
		else:
			i += 2
	return -1


def search(arr, n, x, k):
	val = -1
	for i in range(0, n):
		if arr[i] == x:
			val = i
			break
	return val


def search(arr, n, x, k):
	count = 0
	ans = []
	for i in range(n):
		if arr[i] == x:
			ans.append(i)
			count += 1
	if count < 1:
		return -1
	else:
		return ans[0]


def search(arr, n, x, k):
	n = len(arr)
	i = 0
	ans = -1
	while i < n:
		if arr[i] == x:
			ans = i
			break
		y = max(1, abs(arr[i] - x) // k)
		i += y
	return ans


def search(arr, n, x, k):
	if x not in arr:
		return -1
	if n == 1 and arr[0] == x:
		return 0
	for i in range(len(arr)):
		if arr[i] == x:
			if i > 0 and i < n - 1:
				if abs(arr[i + 1] - arr[i]) <= k and abs(arr[i - 1] - arr[i]) <= k:
					return i
			if i == 0:
				if abs(arr[i + 1] - arr[i]) <= k:
					return i
			if i == n - 1:
				if abs(arr[i - 1]) - arr[i] <= k:
					return i


def search(arr, n, x, k):
	y = 0
	p = 0
	for i in arr:
		if i == x:
			p += 1
	if p >= 1:
		return arr.index(x)
	else:
		return -1


import math

def search(arr, n, x, k):
	i = 0
	while i < n:
		if arr[i] == x:
			return i
		steps = int(math.fabs(x - arr[i]) / k)
		i = i + max(1, steps)
	return -1


def search(arr, n, x, k):
	i = 0
	while i < len(arr):
		if arr[i] == x:
			return i
		jump = abs(x - arr[i]) // k
		jump = max(1, jump)
		i += jump
	return -1


def search(arr, n, x, k):
	try:
		l = arr.index(x)
		return l
	except:
		return -1


def search(arr, n, x, k):
	for i in range(n):
		if arr[i] == x:
			if i == n - 1:
				if arr[i] - arr[i - 1] <= k:
					return i
			elif i == 0:
				if arr[i + 1] - arr[i] <= k:
					return i
			elif arr[i] - arr[i - 1] <= k and arr[i + 1] - arr[i] <= k:
				return i
	return -1


def search(arr, n, x, k):
	i = 0
	while i < n:
		if arr[i] == x:
			return i
		elif abs(arr[i] - x) // k == 0:
			i += 1
		else:
			i = i + abs(arr[i] - x) // k
	return -1


def search(arr, n, x, k):
	ans = 0
	for i in range(n):
		if arr[i] == x:
			ans = i
			break
	else:
		ans = -1
	return ans