Given a sorted array Arr of size N and a number X, you need to find the number of occurrences of X in Arr.
Example 1:
Input:
N = 7, X = 2
Arr[] = {1, 1, 2, 2, 2, 2, 3}
Output: 4
Explanation: 2 occurs 4 times in the
given array.
Example 2:
Input:
N = 7, X = 4
Arr[] = {1, 1, 2, 2, 2, 2, 3}
Output: 0
Explanation: 4 is not present in the
given array.
Your Task:
You don't need to read input or print anything. Your task is to complete the function count() which takes the array of integers arr, n, and x as parameters and returns an integer denoting the answer.
If x is not present in the array (arr) then return 0.
Expected Time Complexity: O(logN)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ Arr[i] ≤ 10^{6}
1 ≤ X ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Complete search

Starter code: #User function Template for python3

class Solution:



	def count(self,arr, n, x):

		# code here

Solutions:
class Solution:

	def count(self, arr, n, x):
		count = 0
		for i in range(len(arr)):
			if arr[i] == x:
				count += 1
		return count


class Solution:

	def bin_search(self, flag, l, r, nums, target):
		ans = -1
		while l <= r:
			mid = (l + r) // 2
			if nums[mid] < target:
				l = mid + 1
			elif nums[mid] > target:
				r = mid - 1
			else:
				ans = mid
				if flag:
					r = mid - 1
				else:
					l = mid + 1
		return ans

	def count(self, nums, n, target):
		l = 0
		r = len(nums) - 1
		left = self.bin_search(True, l, r, nums, target)
		right = self.bin_search(False, l, r, nums, target)
		if left == -1 and right == -1:
			return 0
		return right - left + 1


class Solution:

	def count(self, arr, n, x):
		return arr.count(x)


class Solution:

	def count(self, arr, n, x):
		c = 0
		for i in arr:
			if i == x:
				c += 1
		return c


class Solution:

	def count(self, arr, n, x):
		res = []
		for i in range(n):
			if arr[i] == x:
				res.append(i)
		if len(res) != 0:
			return len(res)
		else:
			return 0


class Solution:

	def count(self, arr, n, x):
		l = 0
		r = n - 1
		left = -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
		if right + left == -2:
			return 0
		else:
			return right - left + 1


class Solution:

	def count(self, arr, n, x):

		def findFirst():
			start = 0
			end = len(arr) - 1
			ans = -1
			while start <= end:
				mid = start + (end - start) // 2
				if arr[mid] == x:
					ans = mid
					end = mid - 1
				elif arr[mid] < x:
					start = mid + 1
				else:
					end = mid - 1
			return ans

		def findLast():
			start = 0
			end = len(arr) - 1
			ans = -1
			while start <= end:
				mid = start + (end - start) // 2
				if arr[mid] == x:
					ans = mid
					start = mid + 1
				elif arr[mid] < x:
					start = mid + 1
				else:
					end = mid - 1
			return ans
		left = findFirst()
		right = findLast()
		if left == -1 and right == -1:
			return 0
		windowSize = right + 1 - left
		return windowSize


class Solution:

	def count1(self, nums, n, x):
		count = 0
		for num in nums:
			if num == x:
				count += 1
		return count

	def count(self, nums, n, x):

		def binarySearch(left, right, searchDirection):
			result = -1
			while left <= right:
				mid = (left + right) // 2
				val = nums[mid]
				if val == x:
					result = mid
					if searchDirection == 'f':
						right = mid - 1
					else:
						left = mid + 1
				elif val > x:
					right = mid - 1
				else:
					left = mid + 1
			return result
		floor = binarySearch(0, n - 1, 'f')
		ceil = binarySearch(0, n - 1, 'c')
		if floor != -1 and ceil != -1:
			return ceil - floor + 1
		return 0


class Solution:

	def count(self, arr, n, x):
		count = 0
		for i in range(n):
			if arr[i] == x:
				count += 1
			else:
				continue
		return count


class Solution:

	def count(self, arr, n, x):
		left = 0
		right = len(arr) - 1
		f = 1
		w = 1
		while left <= right:
			mid = (left + right) // 2
			if arr[mid] == x:
				w = 0
				k = mid
				while k >= 1 and arr[k] == arr[k - 1]:
					f += 1
					k -= 1
				while mid < len(arr) - 1 and arr[mid] == arr[mid + 1]:
					f += 1
					mid += 1
				break
			if arr[mid] == x:
				f += 1
				break
			if arr[mid] < x:
				left = mid + 1
			if arr[mid] > x:
				right = mid - 1
		if w:
			return 0
		return f


class Solution:

	def count(self, arr, n, x):
		l = 0
		r = n - 1
		c = 0
		last = -1
		first = -1
		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
		while l <= r:
			mid = (l + r) // 2
			if arr[mid] == x:
				r = mid - 1
				last = mid
			elif arr[mid] < x:
				l = mid + 1
			else:
				r = mid - 1
		if first == last and first != -1 and (last != -1):
			return 1
		elif first == -1 and last == -1:
			return 0
		return first - last + 1


class Solution:

	def count(self, arr, n, x):
		if x in arr:
			return arr.count(x)
		else:
			return 0


import math

class Solution:

	def first(self, 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(self, 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 count(self, arr, n, x):
		f = self.first(arr, x, 0, n - 1)
		l = self.last(arr, x, 0, n - 1)
		if f != -1:
			return l - f + 1
		else:
			return 0


class Solution:

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


class Solution:

	def count(self, arr, n, x):
		if n <= 0:
			return -1
		elif x not in arr:
			return 0
		else:
			c = 0
			for i in arr:
				if i == x:
					c += 1
			return c


class Solution:

	def count(self, arr, n, x):
		start = 0
		end = n - 1
		while start <= end:
			if arr[start] != x:
				start = start + 1
			if arr[end] != x:
				end = end - 1
			if arr[start] == x and arr[end] == x:
				break
		if start <= end:
			return end - start + 1
		else:
			return 0


import math

class Solution:

	def count(self, arr, n, x):
		count = 0
		start = 0
		end = n - 1
		position = -1
		while start <= end:
			mid = math.ceil((start + end) / 2)
			if arr[mid] == x:
				position = mid
				count = count + 1
				break
			elif arr[mid] > x:
				end = mid - 1
			else:
				start = mid + 1
		if position < 0:
			count = 0
		else:
			left = position - 1
			right = position + 1
			while left >= 0 and arr[left] == x:
				left = left - 1
				count = count + 1
			while right < n and arr[right] == x:
				right = right + 1
				count = count + 1
		return count


class Solution:

	def count(self, arr, n, x):
		first = -1
		last = -1
		count = 0
		for i in range(n):
			if arr[i] == x:
				first = i
				break
		if first == -1:
			return 0
		for i in range(n - 1, -1, -1):
			if arr[i] == x:
				last = i
				break
		count = last - first + 1
		return count


class Solution:

	def count(self, arr, n, x):
		if n == 1:
			if x == arr[0]:
				return 1
		l = 0
		r = n - 1
		while l < r:
			if arr[l] != x:
				l = l + 1
			if arr[r] != x:
				r = r - 1
			if arr[r] == x and arr[l] == x:
				return r - l + 1
				break
		return 0


class Solution:

	def l_find_bsearch(self, nums, target):
		l = 0
		r = len(nums) - 1
		while l <= r:
			mid = (l + r) // 2
			if nums[mid] == target:
				r = mid - 1
			if nums[mid] < target:
				l = mid + 1
			if nums[mid] > target:
				r = mid - 1
		return l

	def r_find_bsearch(self, nums, target):
		l = 0
		r = len(nums) - 1
		while l <= r:
			mid = (l + r) // 2
			if nums[mid] == target:
				l = mid + 1
			if nums[mid] < target:
				l = mid + 1
			if nums[mid] > target:
				r = mid - 1
		return r

	def count(self, nums, n, target):
		if nums == []:
			return 0
		l = self.l_find_bsearch(nums, target)
		if l >= len(nums) or nums[l] != target:
			return 0
		r = self.r_find_bsearch(nums, target)
		if r < 0 or nums[r] != target:
			return 0
		return r - l + 1


class Solution:

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


class Solution:

	def count(self, arr, n, x):
		(i, j) = (0, n - 1)
		while i <= j:
			m = (i + j) // 2
			if arr[m] >= x:
				j = m - 1
			else:
				i = m + 1
		if i < 0 or i >= n or arr[i] != x:
			return 0
		f = i
		(i, j) = (0, n - 1)
		while i <= j:
			m = (i + j) // 2
			if arr[m] <= x:
				i = m + 1
			else:
				j = m - 1
		return j - f + 1


class Solution:

	def count(self, arr, n, x):
		s = 0
		mid = -1
		e = n - 1
		while s <= e:
			mid = s + (e - s) // 2
			if arr[mid] == x:
				break
			elif arr[mid] > x:
				e = mid - 1
			else:
				s = mid + 1
		if mid == -1:
			return 0
		count = 0
		i = mid
		while i >= 0 and arr[i] == x:
			count += 1
			i -= 1
		i = mid + 1
		while i < n and arr[i] == x:
			count += 1
			i += 1
		return count


class Solution:

	def count(self, arr, n, x):
		count = 0
		i = 0
		while i < n:
			if arr[i] == x:
				count += 1
			i += 1
		return count


class Solution:

	def count(self, arr, n, x):
		ctx = 0
		for el in arr:
			if el == x:
				ctx += 1
		return ctx


class Solution:

	def count(self, arr, n, x):

		def search(last=False):
			res = -1
			(low, high) = (0, n - 1)
			while low <= high:
				mid = (low + high) // 2
				if arr[mid] == x:
					res = mid
					if last:
						low = mid + 1
					else:
						high = mid - 1
				elif arr[mid] > x:
					high = mid - 1
				else:
					low = mid + 1
			return res
		firstOccurence = search()
		if firstOccurence == -1:
			return 0
		lastOccurence = search(True)
		return lastOccurence - firstOccurence + 1


class Solution:

	def count(self, arr, n, x):
		try:
			i = arr.count(x)
		except:
			return 0
		return i


class Solution:

	def count(self, arr, n, x):
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		c = 0
		for i in d:
			if i == x:
				return d[i]
				break
			else:
				c += 1
		if c != 0:
			return 0


class Solution:

	def binary(self, arr, n, x):
		s = 0
		e = len(arr) - 1
		while s <= e:
			m = (s + e) // 2
			if arr[m] == x:
				return m
			elif arr[m] < x:
				s = m + 1
			else:
				e = m - 1
		return -1

	def count(self, arr, n, x):
		idx = self.binary(arr, n, x)
		if idx == -1:
			return 0
		k = 1
		left = idx - 1
		while left >= 0 and arr[left] == x:
			k = k + 1
			left = left - 1
		right = idx + 1
		while right < n and arr[right] == x:
			k += 1
			right += 1
		return k


class Solution:

	def count(self, arr, n, x):
		if x not in arr:
			return 0
		l = 0
		r = len(arr) - 1
		while arr[l] != x:
			l = l + 1
		while arr[r] != x:
			r = r - 1
		return r - l + 1


class Solution:

	def count(self, arr, n, x):
		start = -1
		end = -1
		i = 0
		j = n - 1
		while i <= j:
			mid = (i + j) // 2
			if arr[mid] == x:
				start = mid
				j = mid - 1
			elif arr[mid] > x:
				j = mid - 1
			else:
				i = mid + 1
		if start == -1:
			return 0
		i = 0
		j = n - 1
		while i <= j:
			mid = (i + j) // 2
			if arr[mid] == x:
				end = mid
				i = mid + 1
			elif arr[mid] > x:
				j = mid - 1
			else:
				i = mid + 1
		return end - start + 1


class Solution:

	def count(self, arr, n, x):

		def rhs(arr, x):
			low = 0
			high = len(arr) - 1
			while low <= high:
				mid = (low + high) // 2
				if arr[mid] > x:
					high = mid - 1
				else:
					low = mid + 1
			return high

		def lhs(arr, x):
			low = 0
			high = len(arr) - 1
			while low <= high:
				mid = (low + high) // 2
				if arr[mid] >= x:
					high = mid - 1
				else:
					low = mid + 1
			return low
		a = rhs(arr, x)
		b = lhs(arr, x)
		if arr[a] != x:
			return 0
		return a - b + 1


class Solution:

	def count(self, arr, n, x):

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

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


class Solution:

	def count(self, arr, n, x):
		n = len(arr)
		first = -1
		last = -1
		low = 0
		high = n - 1
		while low <= high:
			mid = (low + high) // 2
			if (mid == 0 or x > arr[mid - 1]) and arr[mid] == x:
				first = mid
				break
			elif x > arr[mid]:
				low = mid + 1
			else:
				high = mid - 1
		low = first if first != -1 else 0
		high = n - 1
		while low <= high:
			mid = (low + high) // 2
			if (mid == high or x < arr[mid + 1]) and arr[mid] == x:
				last = mid
				break
			elif x < arr[mid]:
				high = mid - 1
			else:
				low = mid + 1
		count = last - first + 1 if first != -1 else 0
		return count


class Solution:

	def count(self, arr, n, x):
		mydict = dict()
		for i in range(n):
			if arr[i] not in mydict:
				mydict[arr[i]] = 1
			else:
				mydict[arr[i]] += 1
		if x in mydict:
			return mydict[x]
		else:
			return 0