Codestates[Daily Coding] 30번

문제

부분적으로 오름차순 정렬*된 정수의 배열(rotated)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다.

부분적으로 정렬된 배열: 배열을 왼쪽 혹은 오른쪽으로 0칸 이상 순환 이동할 경우 완전히 정렬되는 배열
예시: [4, 5, 6, 0, 1, 2, 3]은 왼쪽으로 3칸 또는 오른쪽으로 4칸 순환 이동할 경우 완전히 정렬됩니다.

입력

인자 1 : rotated
int 타입을 요소로 갖는 배열
rotated[i]는 정수

인자 2 : target

int 타입의 정수
출력
int 타입을 리턴해야 합니다.
주의사항
rotated에 중복된 요소는 없습니다.
target이 없는 경우, -1을 리턴해야 합니다.

처음에 문제를 접근할때 부분적으로 오름차순 되있다는걸 배제하고..
문제를 풀었더니 5개테스트 중 계속 0개가 통과됐었다 ..
사실 이진탐색에대한 개념이 완전히 잘 잡혀있지가 않아서 구글링을 통해
이진탐색에대한 예제코드를 보았지만 잘 이해가 되지않아서
Chat GPT를이용하여 풀었다... 너는참.... 모르는게뭐닣ㅎ....

package com.codestates.coplit; 

public class Solution { 
	public int rotatedArraySearch(int[] rotated, int target) {
       
			 int left=0;
			 int right= rotated.length-1;

			 while(left<=right){

				 int mid= (left+right)/2;

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

				 //왼쪽 절반은 정렬되어있다는 가정
				 if(rotated[left]<=rotated[mid]){

					 if(rotated[left]<=target && target<rotated[mid]){
						 right=mid-1;
					 }else{
						  left=mid+1;
					 }
				 }
				 //오른쪽 절반은 정렬되어있다는 가정
				 else{
					  if(rotated[mid]<target && target<=rotated[right]){
							left=mid+1;
						}else{
							 right=mid-1;
						}
				 }

			 }

			 return -1;
	} 
	
}

부분정렬되있기때문에 이진탐색을 수행해서 현재 검색영역이 왼쪽절반인지, 오른쪽 절반인지 판단

왼쪽 절반이 정렬되어있다는 가정 하에 , target이 현재 영역의 범위에있으면 왼쪽으로 이동
그렇지않으면 오른쪽 영억으로 이동
반대로 오른쪽 절반이 정렬되어있는 가정일때는 , target이 현재 영역의 범위에있으면 오른쪽으로 이동, 그렇지않으면 왼쪽 영역으로 이동