회전 정렬 배열 Javascript 솔루션을 검색합니다.

항목 2
만약 네가 나의 이전 글에서 기억한다면, 우리는 수조에서 가장 긴 연속 서열을 찾기 위한 효율적인 알고리즘을 실현했다.문제의 구체적인 설명은 우리가 선형 검색을 사용하여 이 도전을 해결하는 것을 제한했다.그러나 효율적인 엔지니어로서 우리는 이 알고리즘의 운행 시간을 일부분 높일 수 있는 방법을 찾았다.이 박문을 읽으세요.
오늘 우리는 검색과 관련된 또 다른 알고리즘 도전을 해결하려고 시도할 것이다.이 문제의 독특한 점은 우리가 특정한 검색 알고리즘을 사용하는 데 국한되지 않기 때문에 우리는 이 도전을 효과적으로 해결할 수 있다고 생각하는 모든 알고리즘을 자율적으로 선택할 수 있다는 것이다.

도메인 문제
회전 정렬 수조와 목표 값을 정하고 수조에서 목표 값의 인덱스를 찾습니다.찾지 못하면 -1로 돌아갑니다.모든 물품은 유일무이하다.
예.

입력: ([4,5,6,7,1,2,3]4)

출력: 0

If you'd like to jump straight to the solution, please click here

솔루션
만약 네가 나처럼 이 문제를 해결하는 첫 번째 방법은 바로 뛰어들어가는 것일 수도 있어...tsk..진정해!
지난 몇 주 동안 내가 얻은 게 있다면시작하기 전에 이 문제를 잘 이해해야 한다.
이 문제를 급히 해결하려고 할 때, 선형 검색을 사용해서 이 문제를 해결하기를 원할 수도 있습니다.그래, 너는 틀림없이 답을 얻을 것이다. 그러나 너의 입력 용량이 1000000을 넘으면, 너의 알고리즘의 운행 시간은 O (n) 가 된다.그래서 우리가 이 문제를 어떻게 해결하고 알고리즘의 운행 시간을 높일 수 있느냐고 물어볼 수도 있다.답은 또 다른 유행하는 검색 알고리즘이지만 세부 사항을 깊이 연구하기 전에 이 문제를 먼저 알아보자.

우리는 수조가 항상 정렬될 것이라고 확신한다.

우리는 주어진 입력에 대해 왼쪽과 오른쪽이 수조에서 찾은 항목보다 작을 수도 있다고 추정할 수 있다.
- ([10,11,12,13,2,3,4,5]): 10-12는 13보다 작고 2-5는 13보다 작다.
- [9,1,2,3,4,5,6,7,8]: 9는 4보다 크지만 다른 항목은 4보다 크지 않다.5-8은 4보다 크다.

이 문제를 상상해 보세요. 마치 두 개의 정렬된 그룹을 준 것 같습니다. 그리고 가장 높은 값을 가진 그룹을 만들고 가장 낮은 값을 가진 그룹을 생성한다는 것을 알려줍니다.위의 두 번째 예에 대해 [1.8],[9].9번째 항목이 있는 배열은 첫 번째 입력의 모든 값보다 크기 때문에 첫 번째 값에 있습니다.
다음에 우리는 수조가 항상 정렬된다는 것을 알고 있기 때문에 우리는 자수조의 일부 부분은 항상 정렬된다는 결론을 얻을 수 있다. 우리는 자수조의 기점과 종점을 찾아내기만 하면 된다.

([10,11,12,13,2,3,4,5])-제1자진[10,11,12,13]초[2,3,4,5].

야수를 상대하다.
우리가 이미 이 문제를 이해했으니, 이 도전을 해결할 효과적인 방법을 생각해 낼 때가 되었다.우리가 프로젝트를 정렬할 때, 매우 좋은 검색 알고리즘은 유행하는 2진법 검색이다.우리는 이 문제를 해결하기 위해 이진 검색을 사용할 수 있습니다. 이것은 우리의 운행 시간을 O (n) 에서 O (logn) 로 높일 수 있습니다.그러나 수조가 완전히 정렬되지 않은 것을 감안하여 우리의 해결 방안은 입력된 정렬 부분, 즉 정렬 수조를 사용하는 것을 고려해야 한다.공격 대형으로 들어갑시다.

방주
계속하기 전에,findIndex와 같은 자바스크립트 그룹 내장 방법을 사용하지 않는 이유를 알고 싶을 수도 있습니다.제 개인적인 관점은Javascript로서 우리는 당연히 Javascript가 우리에게 강력한 기능을 제공했다고 생각한다는 것입니다.엔지니어로서 우리는 이런 초강대국들을 어떻게 사용하는지 알아야 할 뿐만 아니라, 그들이 어떻게 일을 하는지, 혹은 그들의 개념이 어떻게 일을 하는지 통제해야 한다.이로써 우리는 이해를 다른 엔지니어나 초급 엔지니어에게 쉽게 옮길 수 있고, 다른 언어로 이러한 개념의 문제를 효과적으로 해결할 수 있다. 그러나 이 언어들은 우리를 위해 토니 스타크 아이언맨 세트를 갖추지 않았다.마지막으로 면접관은 언어에 대한 이해를 평가해야 할 뿐만 아니라 문제를 해결하는 방법을 평가해야 한다.자바스크립트의 슈퍼 기능이 없는 상황에서 이 문제를 해결하기 위해 최선을 다하는 것은 면접관에게 문제를 해결하는 방법을 보여줄 수 있는 기회를 준다.너는 지금 더욱 진일보할 수도 있고, 이 문제는findIndex와 같은 그룹 내장 방법을 사용하여 해결할 수도 있다고 말할 수도 있다.그래서 우리는 계속 전진한다.

층계

두 변수를 정의한다. 예를 들어 (왼쪽과 오른쪽), 왼쪽은 0, 오른쪽은 수조의 마지막 색인(수조 길이-1)이다.

왼쪽과 오른쪽을 합쳐서 2로 나누어 그룹의 중점을 찾습니다.그것을 반올림하여 정수로 하다.

중점에 있는 항목이 목표 값과 같으면 중점 값을 되돌려줍니다.

그렇지 않으면 중점의 항목이 수조의 첫 번째 항목보다 크면 첫 번째 정렬의 하위 수조가 왼쪽과 중점 사이에 있음을 나타낸다.

4.1. 그리고 목표 값이 왼쪽 항목보다 크고 중점보다 작으면 우리의 목표 값이 왼쪽과 중점 사이에 있다는 것을 의미하며 오른쪽을 중점-1로 설정합니다.그렇지 않으면 [왼쪽]을 중점 +1으로 설정합니다.

그렇지 않으면 중점에 있는 항목이 수조의 첫 번째 항목보다 작다는 것은 두 번째 자수조가 입력한 중점을 보존한다는 것을 의미한다.

5.1. 목표 값이 중점 항목보다 크지만 오른쪽 항목보다 작으면 목표 값이 중점과 오른쪽 사이에 있기 때문에 '왼쪽' 을 중점 +1으로 설정합니다.그렇지 않으면 중점-1로 설정합니다.

왼쪽이 오른쪽보다 클 때까지 2단계부터 반복합니다.

7 . 되돌아오다

const rotatedSortedArraySearch = (nums, target) => {
  let left = 0;
  let right = nums.length - 1;

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

    if (nums[mid] === target) {
      console.log(mid);
      return mid;
    } else if (nums[mid] >= nums[left]) {
      if (target >= nums[left] && target <= nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      if (target >= nums[mid] && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  console.log(-1);
  return -1;
};

//test cases
rotatedSortedArraySearch([9, 1, 2, 3, 4, 5, 6, 7, 8], 12);
rotatedSortedArraySearch([9, 1, 2, 3, 4, 5, 6, 7, 8], 9);
rotatedSortedArraySearch([], 1);

결론
이것은 나에게 있어서 매우 까다로운 문제다.당신은 이 문제를 어떻게 해결할 수 있습니까?내가 더 잘할 수 있을까?나는 너의 의견을 듣고 싶다.