이분검색

이진탐색 개념이해

출처: CS50, edwith

문제

임의의 N개의 숫자가 입력으로 주어진다.  

N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면

이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하시오

단 중복값은 존재하지 않는다.

 

🐤입력설명 

첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다. 

두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.

 

🐤출력설명 

첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.

 

🐤입력예제 1

8 32

23 87 65 12 57 32 99 81

 

🐤출력예제 1

3

 

풀이

1. 배열 값을 오름차순 정렬한다.

2. 배열의 인덱스 값이 될 start, mid, end 변수를 설정한다.

3. 얼마나 반복문을 진행할지 정해지지 않았으므로 while 반복문을 사용한다. 조건식에는 배열 첫 인덱스가 끝 인덱스 이하일 때만 반복한다.

4. 배열 중간(mid)인덱스는 (처음 인덱스 + 끝 인덱스) / 2를 한 값을 넣는다

5. 반복문 종료 조건설정. target값이 배열의 중간인덱스값(arr[mid]와 같으면 중간인덱스값+1 을 리턴한다.

6. target값이 배열의 중간인덱스값(arr[mid])보다 작으면 end 값을 mid보다 하나 작은 값으로 바꾼다.

7. target값이 arr[mid]값이 거나 이보다 큰경우엔 start값을 mid보다 하나 큰 값으로 바꾼다.

 

 

코드

function solution(target, arr){
  arr.sort((a, b) => a - b)  			// 1

  let start = 0, end = arr.length-1, mid;  	// 2
  while(start <= end) {  			// 3
    mid = Math.floor((start+end) / 2)  		// 4
    if (target === arr[mid]) return mid + 1  	// 5

    if (target < arr[mid]) end = mid - 1  	// 6
    else start = mid + 1  			// 7
  }
}

let arr=[23, 87, 65, 12, 57, 32, 99, 81];
console.log(solution(32, arr));

 

 

출처

자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의