이진탐색 알고리즘
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
<script>
// 이진탐색
// 정렬되어있어야됨
let arr = [1, 3, 5, 7, 19, 32, 54, 100, 105]; //
let start = 0; // 탐색범위 시작 인덱스
let end = arr.length - 1; // 탐색 범위 끝 인덱스
let find = 5;
let middle = 0 // 시작과 끝의 중간 인덱스
let isFind = false
// middle = parseInt((start + end) / 2);
// if (find == arr[middle]) {
// }
// else if (find > arr[middle]) { // 탐색 범위가 뒤로 -> start
// start = middle;
// }
// else if (find < arr[middle]) { // 탐색 범위가 앞으로 -> end
// end = middle;
// }
while (start <= end) {
middle = parseInt((start + end) / 2);
if (find == arr[middle]) {
isFind = true; // 찾았다
break;
}
else if (find > arr[middle]) {
start = middle + 1;
}
else{
end = middle - 1;
}
}
if(isFind){ //찾았으니 true
console.log(`${find}는(은) ${middle}번째 존재합니다.`)
}
else{ // 못찾았으니 false
console.log("없음")
}
</script>
</body>
</html>이진탐색 개념
이진탐색이란 양 쪽에서 범위를 줄여나가면서 수를 찾는 것이다. 그리고 배열이 무조건 정렬 되어있어야 한다.
범위를 줄일 때 범위의 절반 값을 찾고싶은 수와 비교해서
절반 값 < 찾고싶은 수 → 양 끝 수 중 작은 수를 절반값으로 범위를 줄인다.
절반값 > 찾고싶은 수 → 양 끝 수 중 큰 수를 절반값으로 범위를 줄인다.
범위를 줄이다보면 찾고싶은 수가 나온다.
풀이
1. 변수 선언
let arr = [1, 3, 5, 7, 19, 32, 54, 100, 105]; //
let start = 0; // 탐색범위 시작 인덱스
let end = arr.length - 1; // 탐색 범위 끝 인덱스
let find = 5;
let middle = 0 // 시작과 끝의 중간 인덱스
let isFind = false // 탐색 결과인덱스로 접근해야하기 때문에 시작 인덱스 0, 끝 인덱스는 배열의 길이 - 1과 같다. 중간 인덱스는 숫자형이니 0으로 선언.절반값을 구하는 방법은 양끝 수의 합을 2로 나누고 정수화 하면 된다.
2. 조건문
if (find == arr[middle]) {
isFind = true; // 찾았다
}
else if (find > arr[middle]) {
start = middle + 1;
}
else{
end = middle - 1;
}
if(isFind){ //찾았으니 true
console.log(`${find}는(은) ${middle}번째 존재합니다.`)
}
else{ // 못찾았으니 false
console.log("없음")
}찾고싶은 값과 배열[중간인덱스]가 같으면 찾은 것이다. 중간값보다 find가 더 크면 작은 쪽의 범위를 위로 올려야한다.그래서 start 인덱스에 middle인덱스를 대입하면 된다. else도 비슷한 원리로 작성한다. 여기서 +1 -1을 하는 이유가 중요하다. (내가 개념을 잘못 알고 생각도 못한 부분..) 배열에 존재하지 않는 수를 찾으려고하면어느 순간 start와 end가 같아지는 순간이 존재하는데 그 순간에 무한루프에 빠진다. 무한루프에 빠지는 것을 방지하기 위해+ 1 - 1 을 해줌으로써 서로 엇갈리게 만들어준다.이 말은 start가 end를 넘어서면 배열에 존재하지 않는 수를 찾고 있다는 것이다.
3. 반복문
while (start <= end) {
middle = parseInt((start + end) / 2);
if (find == arr[middle]) {
isFind = true; // 찾았다
break;
}
else if (find > arr[middle]) {
start = middle + 1;
}
else{
end = middle - 1;
}
}
if(isFind){ //찾았으니 true
console.log(`${find}는(은) ${middle}번째 존재합니다.`)
}
else{ // 못찾았으니 false
console.log("없음")
}반복의 범위를 모르기 때문에 while반복문을 사용해준다. while문의 조건은 start가 end가 벗어나기직전 까지니까 등호를 써줘야한다.
start가 end를 넘어서면 배열안의 수를 찾는게 아니니까 반복문을 벗어나고 외부 if - else를 실행해서 "없음"을 출력한다.
isFind에 true를 넣는 방법은 잘 기억해야 한다.
find를 찾았으니 break로 반복문을 벗어나고 바깥 조건문을 실행하면 된다.
'Front-End > 2. JavaScript 자료구조' 카테고리의 다른 글
| [JS] Ex04_Queue구조.html (0) | 2023.06.20 |
|---|---|
| [JS] Ex03_Stack구조.html (0) | 2023.06.20 |
| [JS] Ex01_순차탐색.html (0) | 2023.06.15 |
