Jim Chng jymchng

Interview Question: Finding an Element in a Rotated Sorted Array

Question:

You are given a rotated sorted array of unique integers, meaning the array was originally sorted in ascending order, but then some unknown number of elements were moved from the front to the back. Given this array, write a function search_rotated_array(nums: List[int], target: int) -> int that returns the index of the target in the array. If the target is not present, return -1.

You must write an efficient solution with a time complexity of O(log n).

Example 1:

Interview Question: Finding an Element in a Rotated Sorted Array

Question:

You are given a rotated sorted array of unique integers, meaning the array was originally sorted in ascending order, but then some unknown number of elements were moved from the front to the back. Given this array, write a function search_rotated_array(nums: List[int], target: int) -> int that returns the index of the target in the array. If the target is not present, return -1.

You must write an efficient solution with a time complexity of O(log n).

	from abc import ABC, abstractmethod
	from typing import Optional, Type, Any, Generic, Callable, Self, TypeVar
	from weakref import WeakKeyDictionary

	_T = TypeVar("_T")
	__GLOBAL_INTO_CACHE__: WeakKeyDictionary[Type[Any], Callable[[Self], Any]] = {}


	class IntoMixin(ABC):
	__slots__ = ()

	from abc import ABC, abstractmethod
	from typing import Optional, Type, Any, Generic, Callable, Self, TypeVar, Union
	from weakref import WeakKeyDictionary

	_T = TypeVar("_T")
	__GLOBAL_INTO_CACHE__: WeakKeyDictionary[Type[Any], Callable[[Self], Any]] = (
	WeakKeyDictionary()
	)

	class IntoMixin(ABC):

	import os, sys # Possible to import most packages; go to [Installed Packages] tab, type in the names
	# delimited by comma of the packages you want to install.
	# Click on [Add Package(s)]
	# Then import those packages, e.g. import attrs

	import logging
	from logging import getLogger

	logger = getLogger(__name__)
	logging.basicConfig(level=logging.INFO, format='%(asctime)s %(levelname)-8s [%(filename)s:%(lineno)d] %(message)s', stream=sys.stdout)

	import os, sys # Possible to import most packages; go to [Installed Packages] tab, type in the names
	# delimited by comma of the packages you want to install.
	# Click on [Add Package(s)]
	# Then import those packages, e.g. import attrs

	import logging
	from logging import getLogger

	logger = getLogger(__name__)
	logging.basicConfig(level=logging.INFO, format='%(asctime)s %(levelname)-8s [%(filename)s:%(lineno)d] %(message)s', stream=sys.stdout)

	import os, sys # Possible to import most packages; go to [Installed Packages] tab, type in the names
	# delimited by comma of the packages you want to install.
	# Click on [Add Package(s)]
	# Then import those packages, e.g. import attrs

	import logging
	from logging import getLogger

	logger = getLogger(__name__)
	logging.basicConfig(level=logging.INFO, format='%(asctime)s %(levelname)-8s [%(filename)s:%(lineno)d] %(message)s', stream=sys.stdout)

	import pytest
	from enum import Enum

	class ENVVariant(str):

	__VALID_MEMBERS__ = ["LOCAL", "DEV", "SIT", "UAT", "PREPROD", "PROD"]

	def __new__(cls, value: str):
	members = ENVVariant.__VALID_MEMBERS__
	if isinstance(value, RollYourOwnNewTypeEnum):