코딩일상
[알고리즘] 이진 검색과 선형 검색?? 본문

들어가기전 알고리즘이란??
우리가 작업을 수행하기 필요하기위한 절차와 스텝을 말한다.
알고리즘 또한 자료구조처럼 시간복잡도(Time Complexity)가 낮은 것이 좋다.
이진 탐색을 공부하기 앞서 먼저 선형 탐색에 대해 공부해보겠다.
선형 탐색(Linear Search) 알고리즘??
검색(search)알고리즘 중 하나이다.

그림과 같이 찾는값이 7일 경우 처음부터 하나씩 데이터를 비교해서 원하는 값을 찾는 방식이다.
단점
데이터의 길이가 길어길수록 비례하여 검색속도가 느려진다.
이렇게 데이터가 늘어남에 따라 수행시간이 오래걸리는것을 선형시간 복잡도(Linear Time Complexity)라고 한다.
빅오 표기법 으로나타내자면 O(n)이라고 볼수 있다.

선형검색 알고리즘의 단점을 해결하기 위해 나온 알고리즘이
이진 검색 알고리즘(BinarySearch) 이다.
이진 검색 알고리즘 (BinarySearch) 알고리즘??
이진 검색 알고리즘의 주의 할 점은 모든 배열에서 사용 할 수없다는 것이다.
이진검색 알고리즘은 정렬된 배열(Sorted Array)에서만 사용이 가능하다.
선형 알고리즘은 어느 배열에서든 상관없지만, 이진 검색 알고리즘은 정렬된 배열에서만 사용이 가능하다.

정열된 배열의 단점
정렬이 되지 않은 배열에서 삭제와 추가가 배열의 마지막 데이터 부분에서 추가를 하거나 삭제를 하면 문제 없이
Easy하다 하지만 그 외의 경우에서 아래와 같은 문제가 생긴다.


위 그림과 같이 8이라는 값을 배열에 추가해야할경우
1) 배열에 데이터에서 8보다 큰 값과 작은 값 이 어디 있는지를 파악한다.
2) 추가를하기위해서 각각의 값과 비교를 해야한다
3) 추가를 하기위해 다른 데이터들을 옮겨야한다.
이러한 단점이 있지만 이를 통해서 우린 좀더 빠르게 데이터 검색이 가능해진다.
즉, 이진검색 알고리즘을 사용을 할 수있다.
이진검색 알고리즘 작동방식

이진검색은 선형 검색과 다르게 처음부터 검색을 하지 않고 중간에서 시작을 한다.

그 후 가운데 값이 찾으려는 값보다 큰지 작은지 같은지를 판단후 그 부분에 대해서 검색을 한다.
이러한 동작원리 덕분에 선형검색은 데이터2배가 늘어나면 스텝도 2개가 되지만,
이진 검색의 경우에는 데이터가 2배가 늘어나면 단 1번의 스텝이 늘어나기에 큰 배열을 다룰때 효율적이다.
빅오 표기법은로는 O(log n)이라고 할 수있다.
JavaScript 이진탐색 예시 코드
const binarySearch = (list, target, left, right) => {
let mid = 0;
while (left <= right) {
// 가운데 인덱스
mid = Math.floor((left + right) / 2);
if (list[mid] === target) {
return mid;
}
// 대소 비교로 범위 지정
if (list[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
const sample = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
sample.sort((a, b) => a - b);
// ( 찾을 배열, 탐색할 값, 시작점, 끝점 )
const result = binarySearch(sample, 7, 0, sample.length - 1);
console.log(result);
'Study > CS' 카테고리의 다른 글
[알고리즘] 버블, 선택, 삽입 정렬 알고리즘 (0) | 2022.11.21 |
---|---|
[자료구조] 배열(Array) (0) | 2022.11.17 |
[도입]데이터 구조와 알고리즘은 왜 배워야할까?? (0) | 2022.11.16 |
여러작업을 수행하는 애플리케이션,소프트웨어의 계층구조 (0) | 2022.08.13 |
[CS스터디]고수준 언어에서 프로그램 실현까지!! (0) | 2022.08.04 |