이분법?
이분법은 비선형 방정식(한마디로 말해서 복잡한 식으로 되어있는 방정식)의 해(의 근사값) 컴퓨터를 이용하여 구하는 방법이다. 알고리즘은 다음과 같다.
f(x) = 0의 방정식에서
1. 초기 구간 [x0,x1]과 오차한도 epsilon을 입력
2. x0와 x1의 함수값을 각각 f(x0), f(x1)이라고 한다.
3. f(x0)와 f(x1)의 부호가 다른 경우 아래단계로 간다.(같으면 적용할 수 없다)
4. x0과 x1의 중간값을 x2로 설정한다.
5. 오차를 x0과 x1의 차이라고 할 때, 오차가 epsilon보다 작다면 x2가 해가 된다. 오차가 epsilon보다 크다면 계속해서 아래 단계로 간다.
6. x2의 함수값을 f(x2)로 하고, 오차를 반으로 줄인다.
7. f(x0)과 f(x2)의 부호가 다르다면 x1의 값은 x2의 값이 되고, f(x1)값은 f(x2)의 값으로 할당한다. 만약 f(x0)과 f(x2)의 부호가 같다면 x0의 값은 x2의 값으로 할당하고 f(x0)의 값은 f(x2)의 값으로 할당한다. 즉, 범위를 줄여나간다.
8. 4번(2 설정하는 과정)으로 돌아간다.
위의 과정을 통하여 짠 코드는 다음과 같다.
const Bisection = function (f,x0, x1, epsilon = Number.EPSILON) {
fx0 = f(x0);
fx1 = f(x1);
if (fx0 * fx1 > 0) return 'wrong initial values';
error = Math.abs(x1-x0);
while (error > epsilon) {
error = error / 2;
x2 = (x0 + x1) / 2;
fx2 = f(x2);
if (fx0 * fx2 < 0) {
x1 = x2;
fx1 = fx2;
} else {
x0 = x2;
fx0 = fx2;
}
}
return x2;
}
console.log(x => x**2 - 3, 1, 2)
// 1.7320508075688774 (3의 양의 제곱근과 같다)이진탐색(binarySearch)
이진 탐색 알고리즘이란 이진 트리 검색을 응용한 것이다. 오름차순 정렬이 된 배열이 있을 때 배열의 요소의 인덱스를 찾을 때, 0번째 인덱스부터 찾는 것이 아니라 중간을 기준으로 반으로 나눠서 값을 찾는 방식이다. 알고리즘은 다음과 같다.
- left 변수를 선언하고 값을 0으로 한다.
- right 변수를 선언하고 값을 길이 - 1로 한다.(맨 끝 인덱스)
- left가 right보다 크지 않다면, middle 변수를 선언하고 left와 right의 중간값(배열의 길이가 짝수인 경우에는 정수부분만 취함)으로 할당한다. 그렇지 않다면 7번으로 간다.
- 만약 arr[middle] 과 찾고자 하는 값(target)과 일치하면 middle을 리턴하고 알고리즘 종료.
- target과 arr[middle]을 비교해서 arr[middle]이 더 크다면 오른쪽 범위를 1씩 줄인다. 아니면, 왼쪽 범위를 1씩 키운다.(찾는 범위를 줄여나간다)
- 3번으로 돌아간다.
- -1을 리턴한다.
알고리즘이 이분법과 무엇인가 비슷한 느낌이다. 이분법은 처음 구간을 주고 구간을 조건에 따라 반씩 줄여나가는 방식으로 해를 구하는 방법이고, 이진 탐색 방법은 처음 구간을 주고 조건에 따라서 left or right를 선택하는 방식이다. 이진 탐색 알고리즘을 이용하면 시간복잡도가 O(N)에서 O(logN)으로 비약적으로 줄어든다. 아래는 위의 알고리즘을 따라서 짠 코드이다.
const binarySearch = function (arr, target) {
// TODO : 여기에 코드를 작성합니다.
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;
};
console.log(binarySearch([4, 6, 8, 9, 10, 15], 9)) // 3
Rotated Array Search
회전된 배열 검색은 이진탐색에서 배열만 약간 변형된 상태이다. 배열이 부분적으로 오름차순된 상태이며, 부분적으로 오름차순된 상태란 배열을 왼쪽 혹은 오른쪽으로 0칸 이상 순환 이동할 경우 완전히 정렬되는 상태를 의미한다. 회전된 상태이기 때문에 while문 안의 검색 기준만 추가시키면 된다. 기존 이진 탐색에서는 target과 중간 인덱스만 비교했다. 하지만 회전된 배열에서는 기존 이진탐색에서의 배열과는 달리 arr[left]와 arr[middle]의 대소관계가 명확하지 않다. 따라서 left 인덱스와 middle 인덱스의 대소관계를 먼저 비교한 다음에 left와 target, target과 middle의 대소관계를 일일이 비교해주어야 한다. 아래는 코드이다.
const rotatedArraySearch = function (rotated, target) {
// TODO : 여기에 코드를 작성합니다.
// 단순한 방법
// return rotated.indexOf(target)
// 이진 탐색 방법은 확실히 선형 방정식 이분법(bisection method)과 비슷...
let left = 0;
let right = rotated.length - 1;
while (left <= right) {
let middle = parseInt((left+right)/2);
if (rotated[middle] === target) {
return middle;
}
if (rotated[left] < rotated[middle]) {
if (target < rotated[middle] && rotated[left] <= target) {
right = middle - 1;
} else {
left = middle + 1;
}
} else {
if (target <= rotated[right] && rotated[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
}
return -1;
};
