• 배열과 정수를 입력받아 해당 정수가 해당하는 인덱스를 리턴한다.
• 배열은 부분적으로 정렬 된 상태이다.
  • [4, 5, 6, 0, 1, 2, 3]

시간복잡도 O(n) 풀이 방법

function rotatedArraySearch(arr, target) {
	for(let i=0; i<arr.length; i++) {
		if(arr[i] === target) {
			return i;
		}
	}
	// target이 없는 경우
	return - 1;
}

indexOf 메서드를 이용한 풀이

• 시간복잡도를 고려하지 않은 풀이

function rotatedArraySearch(arr, target) {
	if(!arr.includes(target)) {
		return - 1;
	}
	return arr.indexOf(target);
}

시간복잡도 O(logN) 풀이 방법

• 이진 탐색 트리와 비슷한 방법으로 풀이

function rotatedArraySearch(arr, target) {
	let left = 0;
	let right = arr.length - 1;

	while(left <= right) {
		let mid = Math.floor((left + right) / 2);

		if(target === arr[mid]) {
			return mid;
		}

		// arr[left]가 arr[mid]보다 작은경우
		if(arr[left] < arr[mid]) {
			// target이 arr[left]보다 크거나 같고 arr[mid]보다 작다
			if(target >= arr[left] && target < arr[mid]) {
				// right 이동
				right = mid - 1;
			} else {
					left = mid + 1;
				}
		} else {
				// target이 arr[mid]보다 크고 arr[right]보다 작거나 같다.
				if(target > arr[mid] && target <= arr[right]) {
					// left 이동
					left = mid + 1;
				} else {
						right = mid - 1;
					}
			}
	}
	// target이 없는 경우
	return -1;
}