선형 탐색
선형 탐색(Linear Search)
배열에서 데이터를 탐색하는 알고리즘.
단방향으로 탐색을 시작하여 원하는 데이터를 찾아내는 매우 단순한 알고리즘
배열 [1, 2, 3, 4, 5]에서 4를 탐색한다고 가정하자.
첫번째 탐색
index가 0인 요소와 찾고자 하는 수(4)를 비교한다.
일치하지 않기 때문에 넘어간다.
두번째 탐색
index가 1인 요소와 찾고자 하는 수(4)를 비교한다.
일치하지 않기 때문에 넘어간다.
세번째 탐색
index가 2인 요소와 찾고자 하는 수(4)를 비교한다.
일치하지 않기 때문에 넘어간다.
네번째 탐색
index가 3인 요소와 찾고자 하는 수(4)를 비교한다.
일치하기 때문에 4의 위치 3을 반환한다.
만약 끝까지 탐색했는데 원하는 수가 존재하지 않는다면 -1을 반환한다.
장단점
- 장점
- 구현이 아주 쉽다.
- 정렬되지 않은 리스트에도 사용이 가능하다.
- 단점
- 모든 데이터를 탐색해야 하기에 데이터가 많아질수록 효율이 떨어진다.
선형 탐색(Linear Search) js 코드
const linearSearch = (array, number) => {
for (let i = 0; i < array.length; i++) {
if (array[i] === number) {
// return index value;
return i;
}
}
return -1;
};
const betterLinearSerach = (array, number) => {
let length = array.length;
let left = 0;
let right = length - 1;
let position = -1;
while (left <= right) {
if (array[left] === number) {
position = left;
// return index value;
return position;
}
if (array[right] === number) {
position = right;
// return index value;
return position;
}
left++;
right--;
}
};