이진탐색 문제
오름차순 정렬된 정수의 배열(arr)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다.
const binarySearch = function (arr, target) {
let left = 0;
let right = arr.length - 1;
while(left <= right) {
let mid = Math.floor((left + right) / 2);
if(arr[mid] === target) {
return mid;
} else if(arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
};
코드 해설
1. 문제 전제
- 인자 arr는 오름차순으로 정렬이 되어 있어야 한다.
- 오름차순으로 정렬되어 있어야 arr를 절반씩 나누어서 크기를 비교하여 범위를 좁혀 가는 설계가 유효할 수 있다.
- 인자 arr 배열의 크기가 얼마인지 모르기 때문에 횟수의 정함이 없는 반복을 위해 while 반복을 사용한다.
- while 반복의 조건은 left <= right 일 때까지이다.
1) left > right 인 경우는 right이 음수가 되거나 left가 arr.length를 벗어나기는 경우다.
2. 풀이 설계
1. 가장 작은 인덱스와 가장 큰 인덱스를 각각 변수 left, right 에 저장한다.
2. 인덱스의 중간값을 구해서 변수 mid에 저장한다.
- (left + right) / 2 해서 구하면 된다.
- arr의 길이가 짝수일 경우 (left + right) / 2에 소수점이 있게 되므로 Math.floor로 버린다.
3. arr[mid] 와 target을 비교한다.
1) arr[mid] > target 인 경우
- arr[mid]를 기준으로 배열의 오른쪽에 target이 있을 수 있다.
- 그래서 다음 차례에서 그 배열의 오른쪽에서 탐색을 할 것이기 때문에 left의 값은 mid + 1이 된다.
2) arr[mid] < target 인 경우
- arr[mid]를 기준으로 배열의 왼쪽에 target이 있을 수 있다.
- 다음 차례에서는 배열의 왼쪽에서 탐색을 할 것이기 때문에 right의 값은 mide - 1이 된다.
3) arr[mid] = target 인 경우
- target을 찾았기 때문에 target의 인덱스인 mid를 반환한다.
4. arr[mid]와 target 비교 작업 완료 후에도 반환된 것이 없다면 -1을 반환하여 함수를 종료한다.