[토이10]
binarySearch
문제
오름차순 정렬된 정수의 배열(arr)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다.
입력
인자 1 : arr
number 타입을 요소로 갖는 배열
rotated[i]는 정수
인자 2 : target
number 타입의 정수
출력
number 타입을 리턴해야 합니다.
주의사항
이진탐색 알고리즘(O(logN))을 사용해야 합니다.
단순한 배열 순회(O(N))로는 통과할 수 없는 테스트 케이스가 존재합니다.
target이 없는 경우, -1을 리턴해야 합니다.
시도한 오답
// binary search tree
// arr길이를 이용해서 인덱스로 중간지점을 찾는다.
// 중간 el과 target의 값을 대소비교한다
// 좌측 우측을 판별하고 다시 남은 el들을 줄세워서 처음 단계로 돌아간다
// length가 홀수면 -0.5
// length가 짝수면
// slice로 필요한 부분만 자르기
// target이 el에 있는지 확인 includes
const binarySearch = function (arr, target) {
if (arr.includes(target)) {
if (arr.length % 2 === 1) { // length가 홀수면
if (arr[arr.length/2 - 0.5] > target) { // 보다 크니까 오른쪽 탐색
binarySearch(arr.slice(arr.length/2 - 0.5+1))
} else if (arr[arr.length/2 - 0.5] = target) { // 같으면 그대로 출력
return arr.length/2 - 0.5
} else { // 보다 작으니까 왼쪽 탐색
arr.slice(0, arr.length/2 - 0.5)
binarySearch(arr.slice(arr.length/2 - 0.5))
}
} else if (arr.length % 2 === 0) { // length가 짝수면
if (arr[arr.length/2] > target) { // 보다 크니까 오른쪽 탐색
binarySearch(arr.slice(arr.length/2))
} else if (arr[arr.length/2] = target) { // 같으면 그대로 출력
return arr.length/2
} else { // 보다 작으니까 왼쪽 탐색
arr.slice(0, arr.length/2)
binarySearch(arr.slice(0, arr.length/2))
}
}
} else {
return -1
}
};
ref
const binarySearch = function (arr, target) {
let left = 0,
right = arr.length - 1;
while (left <= right) {
let middle = parseInt((right + left) / 2);
if (arr[middle] === target) {
return middle;
}
if (target < arr[middle]) {
right = middle - 1;
} else {
left = middle + 1;
}
}
return -1;
};// 오... 그렇구나... 아 오늘 문제는 제대로 풀 수 있겠다 싶었는데...👉️👈️
// parseInt
이진탐색 알고리즘 (Binary Search Tree)
- 이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다.
배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다.
X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다.
동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다.
해당 값을 찾을 때까지 이 과정을 반복한다.
탐색하고자 하는 배열이 더이상 존재하지 않으면 찾고자 하는 값이 배열에 존재하지 않는다(더 이상 남은 배열의 요소가 존재하지 않음)는 것으로 판단할 수 있고 탐색을 종료한다. - 장점 : 정렬된 데이터에서 특정한 값을 찾고자할 때 O(logN)의 성능으로 빠르게 값을 찾을 수 있다.
- 구현방법 : 반복 or 재귀
- 이진 탐색의 시간 복잡도는 O(logN)
delilah's journey