이진 탐색

이진 탐색 알고리즘(Binary Search Algorithm)은 이미 정렬되어 있는 배열에서 탐색 범위를 두 부분 리스트로 나눠 절반씩 좁혀가 필요한 부분에서만 탐색하도록 제한하여 원하는 값을 찾는 알고리즘이고 시간복잡도는 0(logN)이다.

기존에 반복문을 통해서 한가지 씩 탐색을 하는 것과 달리 포인트를 2곳을 주어 반을 나누어 탐색을 하는 방식으로 원하는 값을 찾는 알고리즘이다.

만일 위의 그림의 배열에서 찾는 값이 8이라고 예시를 주면 기존에 하나씩 찾는 알고리즘에서는 0부터 하나씩 찾아 9번 반복을 통해서 값을 찾아 낼 수 있지만, 이진 탐색을 통해 찾는 포인트를 시작점과 마지막 지점으로 시작한다면 2번의 반복을 통해 찾아내여 시간적인 이득을 볼 수가 있다.

문제 설명 및 코드 설명

문제

부분적 오름차순으로 정렬된 배열(rotated)과 정수(target)를 입력받아 target의 인덱스를 리턴하시오.

제한사항

• 배열에 중복된 요소는 없다
• 찾는 값이 배열에 없는 경우 -1 return
• 0(logN)

코드

const rotatedArraySearch = function (rotated, target) {
  let leng = rotated.length

  for(let i = 0 ; i < (leng/2) ; i++){
    if(rotated[i] === target ) return i 
    else if(rotated[(leng-1) - i] === target) return (leng-1) - i
  }
  return -1
};

1. 반복문은 배열의 길이에 절반만 반복
2. 배열의 끝부분(leng-1-i)과 배열의 시작부분(i)을 같이 탐색해준다.
3. 만일 찾는 값이 있으면 자신의 index값을 출력
4. 반복문이 끝나도 return이 안된 것은 찾는 값이 없는 것임으로 -1을 출력해준다.

parseInt를 하지 않는 이유는 홀수 일 때에 경우를 대비한 것이다. 예를 들어 배열의 길이가 5일 경우 2.5가 절반이기 때문에 배열의 중간 인덱스는 2일 것이다. 하지만 반복문의 끝 값이 2.5이기 때문에 2까지 검사를 끝낼 뿐더러 맨 위의 if문에서 먼저 걸러지기 때문에 필요없는 코드를 사용하지 않을 수가 있게 된다.