Search in Rotated Sorted Array

항상 어려운 주제들 위주로 공부할려 했던 나한테 현타가 오는 순간인거 같다..어려운 알고리즘들만 공부해서 되게 기본적인 이진탐색같은 문제에 이렇게 애먹는게 너무 슬펐고 내가 약한점들이 뭔지 조금씩 느끼게 되는거같다.

nums로 주어진 벡터는 오름차순으로 정렬 되어있지만 랜덤된 한 구간 (index) 에서 벡터가 회전되있고 타겟 숫자를 O(log n) 시간으로 찾으면 되는 문제이다.

그냥 일반적으로 오름차순 정렬된 벡터에서는 단순 이진탐색을 하여 찾게되면 끝이지만 이런식의 변형 문제에서는 좀 더 다른 접근이 필요한거같다. 내가 접근 했던 방법은 mid 구간을 찾게되면 벡터의 가장 중간값을 가장 첫번째 숫자와 가장 마지막 숫자와 비교해서 어느 부분에서 벡터가 회전됬는지를 확인하였다.

예를 들어 첫번째 샘플에서 mid 값은 7이다. 이 7을 첫번째 숫자인 4와 비교했을때는 더 큰값이므로 첫번째 인덱스부터 mid값인 7까지는 제대로 정렬되어 있는 반면 끝에 숫자 2와 비교했을때는 7 이후에 벡터가 회전되어있다는 거를 알수있다.

이 조건들을 이용해서 천천히 문제를 풀다보면 답이 나오지만 내 실수는 너무 한번에 모든 조건들을 if 문에 넣을려고 했어서 코드가 뒤죽박죽이 되었고 결국 다른 사람의 답 또한 참고하였다. 코딩은 침착해야 하는데 마음이 급해져서 어떻게든 뭘 해볼려고 하다가 오류가 많이났고 실수가 많았던거같다.

배운점:
1. 접근은 천천히 할것
2. 너무 한번에 많은 조건들을 if문에 쓰지말고 단계별로 나눌것