[백준] 1920: 수 찾기 - JS (이분 탐색)

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

N개의 정수 내에서 제공된 M개의 정수들이 존재하는지 확인하세요.

 

 

  접근 방식

 

학습을 목적으로 하여 재귀 함수 방식을 선택하였다. 그리고 해당 문제는 정렬도 함께 사용하기 때문에 정렬을 배우지 않았다면 먼저 정렬이 되어있는 배열을 생성하여 시도해 본다. 먼저는 퀵 정렬을 사용하여 정렬을 하고, 탐색을 하는 것이다.

나는 아직 퀵정렬을 배우기 전 이기에 미리 정렬된 배열로 해보았다. 이 문제는 퀵서치 느낌으로 해결하려고 한다. 

 

 

  풀이

 

quickSearch 함수는 arr와 target을 인자로 받고 boolean 형태의 데이터를 반환한다.

 

먼저 탈출조건은 arr.length가 0일 때는 데이터를 찾지 못한것이기에 false를 반환한다. 

 

pivot을 설정해주는데 Math.floor를 이용하여 홀수를 2로 나누었을 때도 정수가 되게 한다.

하지만 배열의 길이가 2가 되었을 때 해당 코드는 1을 반환하므로 문제가 생긴다. 그러면 모든 상황에서 undefined가 되어 false를 반환하기 때문에 배열의 길이가 2일 때 처리하는 코드를 따로 작성해 주어야 한다.

 

  const pivotIndex = arr.length === 2 ? 0 : Math.floor(arr.length / 2);
  const pivot = arr[pivotIndex];

pivot을 설정하는 코드

 

 

if 문을 통해서 찾는 숫자(target)가 pivot 보다 작은 경우와 큰 경우로 나눈다.

arr인자에는 slice 배열 메서드를 사용하여 pivot 보다 작은 숫자들 혹은 큰 숫자들만 따로 떼어오고, target 값은 그대로 전달해 준다.

 

마지막으로 for문으로 searchMap의 길이만큼 반복해 주면 끝이다. 

 

const hashMap: number[] = [1,2,3,4,7,8,10,23,25,27,38,39,40,44,46,50]; // length == 16
const searchMap: number[] = [1, 40, 8, 27, 51];


function quickSearch(arr: number[], target: number) {	
  if(arr.length === 0) return false;

  const pivotIndex = arr.length === 2 ? 0 : Math.floor(arr.length / 2);
  const pivot = arr[pivotIndex];  
  

  if(pivot === target) return true;
	
  if(target < pivot) {
	return quickSearch(arr.slice(0, pivotIndex), target)
  }
  if(target > pivot) {
	return quickSearch(arr.slice(pivotIndex + 1), target)
  }

}

for (let i = 0; i < searchMap.length; i++) {
  console.log(quickSearch(hashMap, searchMap[i])); 
}

최종코드