[leetcode]33. search-in-rotated-sorted-array

📃 문제 설명

target이 nums안에 있다면 인덱스를 반환하고, 없다면 -1을 반환하면 된다.
이때 시간 복잡도는 O(logN)을 만족해야한다.

🖊 풀이

시간 복잡도를 만족하기 위해서는 이분 탐색법을 사용해야한다.
데이터가 어떠한 값을 기준으로 반반 정렬되어 있기 때문에 이분 탐색법 사용이 가능하다.
즉 반반 정렬되어 있는 기준을 찾아서, first , end 부분으로 나누고 각각 이분 탐색법을 사용하였다.

이분 탐색법은 중간값을 반환하는 조건을 잘 봐야한다.
우선 first 숫자가 mid보다 작거나 같다면 숫자가 증가하고 있는 중이라는 것을 알 수 있다.
이때 이때 target이 mid보다 크거나, first보다 작다면 end부분에서 for문을 돌려야한다.
그러니까 mid값으로 mid+1을 반환하여 다른 부분으로 전환시켜준다.

다른 조건은 위의 설명과 비슷한 맥락으로 이어진다.
이분 탐색법은 전체 데이터를 순회하는 것 보다 빠른 탐색을 내놓기 때문에 익숙해지면 좋을 것 같다.
아직 mid반환 조건이 헷갈리는 부분인 것 같다.