자바스크립트 인터뷰 코딩 테스트 문제 6

정렬된 배열 검색을 완료하는 두 가지 다른 방법을 알아보세요. 무차별 대입 방법과 더 우아한 방법을 살펴보겠습니다.
정렬된 검색
지침
정수와 숫자의 정렬된 배열을 받아들이는 함수를 작성하세요. 해당 숫자의 인덱스가 있으면 반환합니다. 함수는 배열에 없는 대상 값에 대해 -1을 반환해야 합니다.
입력: **정수의 배열, 정수
**출력: **-1부터의 정수.
**솔루션 1

1   function search(numbers, target) {
2     for(let i = 0; i < numbers.length; i++) {
3       if(numbers[i] === target) {
4         return i;
5       }
6     }
7
8     return -1;
9   }

이 솔루션은 매우 간단합니다. 우리는 배열을 살펴보고 목표를 찾으려고 노력합니다.
시간
전체 배열을 살펴보므로 시간 복잡도는 O(n)입니다.
우주
설정된 수의 변수를 저장하므로 공간 복잡도는 0(1)입니다.
이진 검색
우리는 더 나은 해결책을 제시할 수 있습니다. 배열이 정렬되어 있기 때문에 찾고 있는 인덱스를 찾을 때까지 기본적으로 배열 주위를 이동할 수 있습니다.
단어 찾기
사전에서 단어를 찾는다고 상상해 보십시오. 원하는 단어를 찾을 때까지 모든 단어를 살펴보는 것이 효율적일까요? 아니, 그것은 끔찍하게 비효율적일 것이다.
더 나은 방법은 사전을 반쯤 여는 것입니다. 우리 단어가 알파벳순으로 중간 페이지의 단어 앞에 있으면 우리 단어가 책의 전반부에 있다는 것을 알 수 있습니다.
그런 다음 사전을 통해 ~1/4로 뒤집을 수 있습니다. 다시 위의 과정을 반복하면 남은 페이지의 절반을 더 제거할 수 있습니다.
단어를 찾을 때까지 위의 단계를 반복해서 반복할 수 있습니다. 이렇게 하면 사전이 방대하더라도 각 단어를 개별적으로 살펴보는 것보다 훨씬 빠르게 단어를 찾을 수 있습니다.
스케일링
사실, 더 많은 단어를 추가하여 사전의 크기를 두 배로 늘리면 이 과정을 한 번만 더 반복하면 됩니다. 사전이 훨씬 두꺼워도 더 이상 할 일이 아닙니다.
이 접근 방식을 코드로 바꿔 보겠습니다.
솔루션 2

1   function binarySearch(numbers, target) {
2     let startindex = 0;
3     let endindex = numbers.length - 1;
4
5     if(target < numbers[startindex] || target > numbers[endindex]) {
6       return -1;
7     }
8
9       while(true) {
10    if(numbers[startindex] === target) {
11      return startindex:
12      }
13
14      if(numbers[endindex] === target) {
15        return endindex; }
17
18  if(endindex - startindex <= l) {
19  //indicates the number isn't present
20  return -1;
22
23  const middleindex = Math.floor((startindex + endindex)/2);
24
25      if(target > numbers[middlelndex]) {
26        Startindex = middlelndex + 1;
27      } else if(target < numbers[middlelndex]) {
28        endindex = middleindex - 1;
29      } else {
30        return middlelndex;
31      }

작동 방식
대상이 배열의 범위 내에 있는지 확인하고 반환하는 것으로 시작합니다.
그렇지 않으면 거짓입니다.

루프에서 먼저 대상이 배열의 시작 및 끝 값과 같은지 확인합니다. 그런 다음 대상이 중앙 값보다 크거나 작은지 확인합니다.
중앙에 있는 값보다 작으면 배열의 전반부 어딘가에 있을 것임을 알 수 있습니다. 우리는 그것에 집중할 수 있습니다.
더 크면 전반부에 있을 수 없다는 것을 알기 때문에 후반부를 찾는 데 집중할 수 있습니다.
계속해서 우리는 그 위치에 가까워질 때까지 검색해야 하는 양을 절반으로 줄입니다. 도중에 찾으면 중지하고 인덱스를 반환할 수 있습니다.