Given a sorted array arr containing n elements with possibly duplicate elements, the task is to find indexes of first and last occurrences of an element x in the given array.
Example 1:
Input:
n=9, x=5
arr[] = { 1, 3, 5, 5, 5, 5, 67, 123, 125 }
Output:  2 5
Explanation: First occurrence of 5 is at index 2 and last
             occurrence of 5 is at index 5. 
 
Example 2:
Input:
n=9, x=7
arr[] = { 1, 3, 5, 5, 5, 5, 7, 123, 125 }
Output:  6 6 
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function find() that takes array arr, integer n and integer x as parameters and returns the required answer.
Note: If the number x is not found in the array just return both index as -1.
 
Expected Time Complexity: O(logN)
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{7}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #User function Template for python3





def find(arr,n,x):

    # code here



Solutions:
def find(arr, n, x):
	listo = []
	for i in range(n):
		if arr[i] == x:
			listo.append(i)
	if len(listo) == 0:
		return (-1, -1)
	else:
		return (min(listo), max(listo))


def find(arr, n, x):
	res = []
	for i in range(n):
		if arr[i] == x:
			res.append(i)
	if len(res) == 0:
		return (-1, -1)
	else:
		return (res[0], res[-1])


def find(arr, n, x):
	count = arr.count(x)
	if count == 0:
		return (-1, -1)
	li = []
	for i in range(n):
		if arr[i] == x:
			li.append(i)
	return (li[0], li[-1])


def find(arr, n, x):
	farr = [-1, -1]
	for i in range(0, n):
		if arr[i] == x:
			farr[0] = i
			break
	for j in range(n - 1, -1, -1):
		if arr[j] == x:
			farr[1] = j
			break
	return farr


def find(arr, n, x):
	index = []
	for i in range(n):
		if arr[i] == x:
			index.append(i)
	if len(index):
		return (index[0], index[-1])
	return (-1, -1)


def find(arr, n, x):
	li = []
	for (i, ele) in enumerate(arr):
		if ele == x:
			li.append(i)
	if len(li) == 0:
		return (-1, -1)
	return (li[0], li[-1])


def find(arr, n, x):
	a = -1
	b = -1
	for (i, ele) in enumerate(arr):
		if ele == x:
			if a == -1:
				a = i
			b = i
	if a == -1:
		return (-1, -1)
	return (a, b)


def find(arr, n, x):
	first_occurrence = -1
	last_occurrence = -1
	for (i, ele) in enumerate(arr):
		if ele == x:
			if first_occurrence == -1:
				first_occurrence = i
			last_occurrence = i
	if first_occurrence == -1:
		return (-1, -1)
	return (first_occurrence, last_occurrence)


def find(arr, n, x):
	i = -1
	j = -1
	for a in range(n):
		if arr[a] == x:
			i = a
			break
	for b in range(n):
		if arr[b] == x:
			j = b
	return [i, j]


def find(arr, n, x):
	left = -1
	l = 0
	r = n - 1
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] == x:
			left = mid
			r = mid - 1
		elif arr[mid] > x:
			r = mid - 1
		else:
			l = mid + 1
	l = 0
	r = n - 1
	right = -1
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] == x:
			right = mid
			l = mid + 1
		elif arr[mid] > x:
			r = mid - 1
		else:
			l = mid + 1
	return [left, right]


def find(arr, n, x):
	sub = [] * 10000000
	for i in range(n):
		if arr[i] == x:
			sub.append(i)
	if len(sub) == 0:
		return (-1, -1)
	else:
		return (sub[0], sub[-1])


import bisect

def find(arr, n, x):
	a = []
	for i in range(n):
		if arr[i] == x:
			a.append(i)
	if len(a) == 0:
		return (-1, -1)
	else:
		return (a[0], a[-1])


def find(arr, n, x):
	first = -1
	(low, high) = (0, n - 1)
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] == x:
			first = mid
			high = mid - 1
		elif arr[mid] < x:
			low = mid + 1
		else:
			high = mid - 1
	last = -1
	(low, high) = (0, n - 1)
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] == x:
			last = mid
			low = mid + 1
		elif arr[mid] < x:
			low = mid + 1
		else:
			high = mid - 1
	return (first, last)


def find(arr, n, x):
	findex = -1
	lindex = -1
	flag = 0
	for i in range(n):
		if arr[i] == x:
			if flag == 0:
				findex = i
				lindex = i
				flag = 1
			else:
				lindex = i
	return (findex, lindex)


def find(arr, n, key):

	def findVal(arr, key, low, high, flag):
		if low > high:
			return -1
		mid = low + (high - low) // 2
		if arr[mid] < key:
			return findVal(arr, key, mid + 1, high, flag)
		elif arr[mid] > key:
			return findVal(arr, key, low, mid - 1, flag)
		if flag:
			if mid == 0 or (mid > 0 and arr[mid - 1] != key):
				return mid
			else:
				return findVal(arr, key, low, mid - 1, flag)
		else:
			if mid == len(arr) - 1 or (mid < len(arr) and arr[mid + 1] != key):
				return mid
			return findVal(arr, key, mid + 1, high, flag)
	return (findVal(arr, key, 0, len(arr) - 1, True), findVal(arr, key, 0, len(arr) - 1, False))


def find(arr, n, x):
	left = -1
	right = -1
	for i in range(len(arr)):
		if arr[i] == x and left == -1:
			left = i
		elif arr[i] == x:
			right = i
	if right == -1:
		right = left
	return (left, right)


def find(arr, n, x):
	nums = arr
	target = x

	def bin_search(nums, target, leftbias):
		l = 0
		r = len(nums) - 1
		i = -1
		while l <= r:
			m = (l + r) // 2
			if target > nums[m]:
				l = m + 1
			elif target < nums[m]:
				r = m - 1
			else:
				i = m
				if leftbias:
					r = m - 1
				else:
					l = m + 1
		return i
	left = bin_search(nums, target, True)
	right = bin_search(nums, target, False)
	return [left, right]


def find(arr, n, x):
	first = -1
	last = -1
	for (i, val) in enumerate(arr):
		if first == -1 and val == x:
			first = i
			last = i
		elif last != -1 and val == x:
			last = i
		elif val > x:
			break
	return [first, last]


def find(arr, n, x):
	first = -1
	last = -1
	for i in range(0, n):
		if x != arr[i]:
			continue
		if first == -1:
			first = i
		last = i
	if first != -1:
		return (first, last)
	else:
		return (-1, -1)


def find(arr, n, x):
	pos = []
	for i in range(0, n):
		if arr[i] == x:
			pos.append(i)
			break
	for i in range(n - 1, -1, -1):
		if arr[i] == x:
			pos.append(i)
			break
	if pos:
		return pos
	return (-1, -1)


def find(arr, n, x):
	first = -1
	last = -1
	for i in range(n):
		if arr[i] == x:
			first = i
			break
	for j in range(n):
		if arr[n - 1 - j] == x:
			last = n - 1 - j
			break
	return (first, last)


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


def find(arr, n, x):
	if arr.count(x) == 0:
		return [-1, -1]
	else:
		first_index = arr.index(x)
		arr.reverse()
		last_index = arr.index(x) + 1
		return [first_index, n - last_index]


def find(arr, n, x):
	l = 0
	r = n - 1
	first = -1
	res = []
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] == x:
			first = mid
			l = mid + 1
		elif arr[mid] < x:
			l = mid + 1
		else:
			r = mid - 1
	l = 0
	r = n - 1
	last = -1
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] == x:
			last = mid
			r = mid - 1
		elif arr[mid] < x:
			l = mid + 1
		else:
			r = mid - 1
	res.append(last)
	res.append(first)
	return res


def find(arr, n, x):
	if x in arr:
		val1 = arr.index(x)
		rev = arr[::-1]
		val2 = n - rev.index(x) - 1
		return [val1, val2]
	else:
		return [-1, -1]


def find(arr, n, x):
	if arr[0] == x and arr[n - 1] == x:
		return [0, n - 1]
	occurances = []
	first_occurance = firstOccurance(arr, x)
	occurances.append(first_occurance)
	if occurances[0] == -1:
		occurances.append(-1)
		return occurances
	last_occurance = lastOccurance(arr, x)
	occurances.append(last_occurance)
	return occurances

def firstOccurance(arr, x):
	if arr[0] == x:
		return 0
	left = 0
	right = len(arr) - 1
	while left <= right:
		mid = left + (right - left) // 2
		if arr[mid] == x:
			if arr[mid - 1] == x:
				right = mid - 1
			else:
				return mid
		elif arr[mid] > x:
			right = mid - 1
		else:
			left = mid + 1
	return -1

def lastOccurance(arr, x):
	if arr[n - 1] == x:
		return n - 1
	left = 0
	right = len(arr) - 1
	while left <= right:
		mid = left + (right - left) // 2
		if arr[mid] == x:
			if arr[mid + 1] == x:
				left = mid + 1
			else:
				return mid
		elif arr[mid] > x:
			right = mid - 1
		else:
			left = mid + 1
	return -1


def find(arr, n, x):
	fst = -1
	lst = -1
	for i in range(n):
		if arr[i] == x:
			lst = i
		if fst == -1 and arr[i] == x:
			fst = i
	return (fst, lst)


def find(arr, n, x):
	(l, h) = (0, n - 1)
	res = f(arr, x, l, h)
	res1 = s(arr, x, l, h)
	return (res, res1)

def f(arr, x, l, h):
	a = -1
	while l <= h:
		m = (l + h) // 2
		if arr[m] == x:
			a = m
			h = m - 1
		elif x > arr[m]:
			l = m + 1
		else:
			h = m - 1
	return a

def s(arr, x, l, h):
	a1 = -1
	while l <= h:
		m = (l + h) // 2
		if arr[m] == x:
			a1 = m
			l = m + 1
		elif x > arr[m]:
			l = m + 1
		else:
			h = m - 1
	return a1


import math

def first(arr, x, low, high):
	while low <= high:
		mid = math.floor((low + high) / 2)
		if arr[mid] > x:
			high = mid - 1
		elif arr[mid] < x:
			low = mid + 1
		elif mid == 0 or arr[mid] != arr[mid - 1]:
			return mid
		else:
			high = mid - 1
	return -1

def last(arr, x, low, high):
	while low <= high:
		mid = math.floor((low + high) / 2)
		if arr[mid] > x:
			high = mid - 1
		elif arr[mid] < x:
			low = mid + 1
		elif mid == n - 1 or arr[mid] != arr[mid + 1]:
			return mid
		else:
			low = mid + 1
	return -1

def find(arr, n, x):
	a = first(arr, x, 0, n - 1)
	b = last(arr, x, 0, n - 1)
	return (a, b)


def find(arr, n, x):
	d = {}
	for (key, value) in enumerate(arr):
		d[key] = value
	l = []
	for i in d.keys():
		if d[i] == x:
			l.append(i)
	if len(l):
		return (min(l), max(l))
	else:
		return (-1, -1)


def find(arr, n, x):
	first_occurrence = -1
	last_occurrence = -1
	n = len(arr)
	low = 0
	high = n - 1
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] == x:
			first_occurrence = mid
			high = mid - 1
		elif arr[mid] < x:
			low = mid + 1
		else:
			high = mid - 1
	low = 0
	high = n - 1
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] == x:
			last_occurrence = mid
			low = mid + 1
		elif arr[mid] < x:
			low = mid + 1
		else:
			high = mid - 1
	return (first_occurrence, last_occurrence)


def find(arr, n, x):
	f = 0
	l = []
	for i in range(n):
		if arr[i] == x:
			l.append(i)
	if len(l) > 0:
		return (l[0], l[len(l) - 1])
	else:
		return (-1, -1)


def find(arr, n, x):
	f = 0
	l = 0
	flag = 0
	for i in range(n):
		if arr[i] == x:
			if flag == 0:
				f = i
				l = i
				flag = 1
			else:
				l = i
	if flag == 0:
		return (-1, -1)
	return (f, l)


def find(arr, n, x):

	def firstSearch(arr, tar, n):
		(i, j) = (0, n - 1)
		res = -1
		while i <= j:
			mid = (i + j) // 2
			if arr[mid] == tar:
				res = mid
				j = mid - 1
			elif arr[mid] < tar:
				i = mid + 1
			else:
				j = mid - 1
		return res

	def lastSearch(arr, tar, n):
		(i, j) = (0, n - 1)
		res = -1
		while i <= j:
			mid = (i + j) // 2
			if arr[mid] == tar:
				res = mid
				i = mid + 1
			elif arr[mid] < tar:
				i = mid + 1
			else:
				j = mid - 1
		return res
	return [firstSearch(arr, x, n), lastSearch(arr, x, n)]


def find(arr, n, x):
	first = -1
	c = 0
	l = []
	for i in range(n):
		if arr[i] == x and c > 0:
			c = c + 1
		if arr[i] == x and c == 0:
			first = i
			c = c + 1
	if first == -1:
		l.extend((-1, -1))
	else:
		l.extend((first, first + c - 1))
	return l


def find(arr, n, x):
	if x not in arr:
		return (-1, -1)
	return (arr.index(x), n - arr[::-1].index(x) - 1)


def find(arr, n, x):
	if x not in arr:
		return [-1, -1]
	f = arr.index(x)
	for i in range(n - 1, -1, -1):
		if arr[i] == x:
			b = i
			return [f, b]
			break


def find(arr, n, x):
	ans = [-1, -1]

	def f(first):
		s = 0
		l = n - 1
		while s <= l:
			mid = (s + l) // 2
			if arr[mid] < x:
				s = mid + 1
			elif arr[mid] > x:
				l = mid - 1
			elif first:
				ans[0] = mid
				l = mid - 1
			else:
				ans[1] = mid
				s = mid + 1
	f(True)
	f(False)
	return ans


def find(arr, n, x):
	ind1 = -1
	for i in range(n):
		if arr[i] == x:
			ind1 = i
			break
	if ind1 >= 0:
		ind2 = ind1 + arr.count(x) - 1
	else:
		ind2 = -1
	return (ind1, ind2)


def find(arr, n, x):
	arr = list(arr)
	(first, last) = (-1, -1)
	(lo, hi) = (0, n - 1)
	while lo <= hi:
		mid = (lo + hi) // 2
		if x == arr[mid]:
			first = mid
			hi = mid - 1
		elif x > arr[mid]:
			lo = mid + 1
		else:
			hi = mid - 1
	(lo, hi) = (0, n - 1)
	while lo <= hi:
		mid = (lo + hi) // 2
		if x == arr[mid]:
			last = mid
			lo = mid + 1
		elif x > arr[mid]:
			lo = mid + 1
		else:
			hi = mid - 1
	return (first, last)


def find(arr, n, x):

	def search(x):
		(left, right) = (0, n - 1)
		while left <= right:
			mid = (left + right) // 2
			if arr[mid] < x:
				left = mid + 1
			else:
				right = mid - 1
		return left
	a = search(x)
	b = search(x + 1) - 1
	if a <= b:
		return [a, b]
	return [-1, -1]


def find(arr, n, x):
	(l, r) = (0, n - 1)
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] == x:
			i = mid
			j = mid
			while i > 0 and arr[i - 1] == x:
				i -= 1
			while j < n - 1 and arr[j + 1] == x:
				j += 1
			return (i, j)
		elif arr[mid] > x:
			r = mid - 1
		else:
			l = mid + 1
	return (-1, -1)


def find(arr, n, x):
	a = 0
	d = 0
	if x not in arr:
		a = -1
		d = -1
		return (a, d)
	else:
		for i in range(n):
			if arr[i] == x:
				d = i
		a = d - arr.count(x) + 1
		return (a, d)


def find(arr, n, x):
	first = -1
	last = -1
	start = 0
	end = n - 1
	while start <= end:
		mid = (start + end) // 2
		if arr[mid] < x:
			start = mid + 1
		elif arr[mid] > x:
			end = mid - 1
		else:
			first = mid
			end = mid - 1
	start = 0
	end = n - 1
	while start <= end:
		mid = (start + end) // 2
		if arr[mid] < x:
			start = mid + 1
		elif arr[mid] > x:
			end = mid - 1
		else:
			last = mid
			start = mid + 1
	return (first, last)


def find(arr, n, x):
	list1 = []
	if x not in arr:
		return [-1, -1]
	list1.append(arr.index(x))
	for i in range(len(arr) - 1, -1, -1):
		if arr[i] == x:
			list1.append(i)
			break
	return list1


def find(arr, n, x):
	i = 0
	j = n - 1
	f1 = 0
	f2 = 0
	while f1 * f2 == 0 and i <= j:
		if arr[i] == x:
			f1 = 1
		else:
			i += 1
		if arr[j] == x:
			f2 = 1
		else:
			j -= 1
	if i > j:
		return (-1, -1)
	return (i, j)


def find(arr, n, x):
	if x in arr:
		a = []
		for i in range(0, n):
			if arr[i] == x:
				a.append(i)
		return [a[0], a[-1]]
	else:
		return [-1, -1]


def find(arr, n, x):
	if len(arr) == 0:
		return (-1, -1)
	if x not in arr:
		return (-1, -1)
	for i in range(n):
		if arr[i] == x:
			start = i
			break
	for i in range(n - 1, -1, -1):
		if arr[i] == x:
			end = i
			break
	return (start, end)


def find(arr, n, x):
	ans = -1
	start = 0
	end = n - 1
	while start <= end:
		mid = (start + end) // 2
		if x == arr[mid]:
			ans = mid
			start = mid + 1
		elif x > arr[mid]:
			start = mid + 1
		else:
			end = mid - 1
	start = 0
	end = n - 1
	res = -1
	while start <= end:
		mid = (start + end) // 2
		if x == arr[mid]:
			res = mid
			end = mid - 1
		elif x > arr[mid]:
			start = mid + 1
		else:
			end = mid - 1
	return (res, ans)


def find(arr, n, x):
	if x in arr:
		n1 = arr.index(x)
		for i in range(len(arr) - 1, -1, -1):
			if arr[i] == x:
				n2 = i
				break
		return (n1, n2)
	else:
		return (-1, -1)


def find(arr, n, x):
	l = []
	for i in range(0, len(arr)):
		if arr[i] == x:
			l.append(i)
			break
	if len(l) == 0:
		l.append(-1)
	for i in range(len(arr) - 1, -1, -1):
		if arr[i] == x:
			l.append(i)
			break
	if len(l) == 1:
		l.append(-1)
	return l


def find(arr, n, x):
	start = end = -1
	if x not in arr:
		return (-1, -1)
	else:
		for i in range(n):
			if arr[i] == x:
				start = i
				end = i
				for j in range(i, n):
					if arr[j] == x:
						end = j
				return (start, end)


def find(arr, n, x):
	flag = 0
	for i in range(0, len(arr)):
		if arr[i] == x:
			a = i
			flag = 1
			break
	if flag == 0:
		a = -1
		flag = 0
	for i in range(len(arr) - 1, -1, -1):
		if arr[i] == x:
			b = i
			flag = 1
			break
	if flag == 0:
		b = -1
	l = [a, b]
	return l


def find(arr, n, x):
	m = 0
	if x not in arr:
		k = -1
		p = -1
		return (p, k)
	else:
		for i in range(n):
			if x == arr[i]:
				m = i
	ans = m - arr.count(x) + 1
	return (ans, m)


def find(arr, n, x):
	si = 0
	ei = len(arr) - 1
	ans = [-1, -1]
	while si <= ei:
		mid = (si + ei) // 2
		if arr[mid] == x:
			ans[0] = mid
			ei = mid - 1
		elif arr[mid] < x:
			si = mid + 1
		else:
			ei = mid - 1
	si = 0
	ei = len(arr) - 1
	while si <= ei:
		mid = (si + ei) // 2
		if arr[mid] == x:
			ans[1] = mid
			si = mid + 1
		elif arr[mid] < x:
			si = mid + 1
		else:
			ei = mid - 1
	return ans


import math

def find(arr, n, x):
	first = -1
	last = -1
	start = 0
	end = n - 1
	result = []
	position = -1
	while start <= end:
		mid = math.ceil((start + end) / 2)
		if arr[mid] == x:
			position = mid
			break
		if arr[mid] > x:
			end = mid - 1
		if arr[mid] < x:
			start = mid + 1
	if position != -1:
		temp = position
		while temp >= 0 and arr[temp] == x:
			temp = temp - 1
		first = temp + 1
		temp = position
		while temp <= n - 1 and arr[temp] == x:
			temp = temp + 1
		last = temp - 1
	result.append(first)
	result.append(last)
	return result


def find(arr, n, x):
	low = 0
	high = n - 1
	while low <= high:
		if arr[low] == x and arr[high] == x:
			return (low, high)
		elif arr[low] == x:
			high = high - 1
		elif arr[high] == x:
			low = low + 1
		else:
			low = low + 1
			high = high - 1
	return (-1, -1)


def find(arr, n, x):
	l = []
	if x not in arr:
		return (-1, -1)
	for i in range(0, n):
		if arr[i] == x:
			l.append(i)
	r = min(l)
	m = max(l)
	return (r, m)


def find(arr, n, x):
	f = ''
	l = ''
	for i in range(n):
		if f == '' and arr[i] == x:
			f = i
		if l == '' and arr[n - i - 1] == x:
			l = n - i - 1
		if f != '' and l != '':
			return (f, l)
	return (-1, -1)


def find(arr, n, x):
	left = 0
	right = n - 1
	while left <= right:
		mid = (left + right) // 2
		if arr[mid] == x:
			result = [mid, mid]
			decr = mid - 1
			while decr >= 0 and arr[decr] == x:
				decr -= 1
			result[0] = decr + 1
			incr = mid + 1
			while incr < n and arr[incr] == x:
				incr += 1
			result[1] = incr - 1
			return result
		elif arr[mid] < x:
			left = mid + 1
		else:
			right = mid - 1
	return [-1, -1]


def find(arr, n, x):
	l = []
	i = 0
	while i < n:
		if arr[i] == x:
			l.append(i)
		i += 1
	if len(l) == 0:
		return [-1, -1]
	return [l[0], l[-1]]