33. Search in Rotated Sorted Array

아 o(logn) 꼴도 보기싫다 ㅋㅋㅋㅋ.. 지문이 제법 길지만, 뭐 대충  이거는 pivot 에 의해 정렬 이 된 상태의 배열이 주어진다. 위에 예시가 착하게 나와 있으니 예시를 보면 이해하기 쉽다. 음 ? 이해가 왜 미디엄 레벨 이지 ?

좌우 포인터 잡고 하나씩 줄여가기로 결정

class Solution {
  public int search(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1;
    int idx = -1; // set default as -1
    while (left <= right) {
      if (nums[left] == target) {
        idx = left;
        break;
      } else {
        left++;
      }
      if (nums[right] == target) {
        idx = right;
        break;
      } else {
        right--;
      }
    }
    return idx;
  }
}

특별할것 하나 없는 코드이다. 말 그대로 -1 을 디폴트로 설정해서 좌우 번갈아 가면서 찾아준다. 주어진 문제에서 숫자는 고유하기 떄문에 이러한 방법이 가능하다. 

다른사람들의 코드를 보자.

public class Solution {
public int search(int[] A, int target) {
    int lo = 0;
    int hi = A.length - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2; // 미드 값 구하기
        if (A[mid] == target) return mid;
        
        if (A[lo] <= A[mid]) { 
        //현재 미드값 과 레프트 값의 비교 만약 이게 성립이 된다면 현재 범위는 로테이트 된 값 이 있는 부분이다.
            if (target >= A[lo] && target < A[mid]) {
                hi = mid - 1; //로테이된 왼쪽 부분에 위치하는 조건이다. 
            } else {
                lo = mid + 1; // 로테이트된 오른쪽 부분에 위치하는 조건이다.
            }
        } else {
            if (target > A[mid] && target <= A[hi]) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    return A[lo] == target ? lo : -1;
}

이 사람은 이분탐색 그대로 구현했다. 대신 미드 값에 따른 이동 포인터를 좌우 비교를 통해 현재 진행되는 방향이 로테이트 된 방향인지 아닌지를 모두 체크하는 if 문을 넣어 주었는데 비교적 코드가 직관적 이여서 가져왔다.

음  만약 1,2,3,4,5,6,7 이란 코드가 있고 4,5,6,7,0,1,2,3 이렇게 피벗 4 에 변경이 된다면 4 5 6 7  / 0 1 2 3 이렇게 나누어서 생각해 볼수 있다 여기서 찝은 미드의 값과 왼쪽 과 오른쪽 비교를 해주었을때  어느 부분을 찝었는 지 알수 있다. 또한 타겟을 이용해 범위를 명확히 줄여 나가는 것이 참 신기한 아이디어 같다.

왼쪽 비교를 할때는 4 와 미드값 7 그리고 타겟

오른쪽 비교를 할때는 미드값 7 과 마지막 값 3   그리고 타겟

이렇게 현재 잡힌 미드 와 타겟 의 값을 이용해 반대편을 계속 완전히 버려줄수 있다. 

 

정말 고수들은 많다.