[CS] 알고리즘 02 : 선형 검색 (Linear search)

선형 검색 (Linear search)

선형검색은 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색하는 알고리즘입니다.

선형 검색은 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 사용합니다.

선형 검색의 동작 과정

만약 23이라는 값을 찾고 있다면
1. 배열/라스트를 하나씩 순회하면서 찾는 값과 비교한다.
2. 원하는 값을 찾았을 경우 값을 반환해준다.

선형 검색의 성능

최선의 경우 -> O(1)
: 찾고자 하는 값이 배열의 첫 번째 위치에 있는 경우 한 번의 비교로 값을 찾을 수 있다.

평균의 경우 -> O(n)

최악의 경우 -> O(n)
: 최악의 경우, 찾고자 하는 값이 배열의 마지막에 있거나 배열에 존재하지 않는 경우, 모든 요소를 확인해야한다.

선형 검색 코드 (Swift)

배열 arr과 target을 받았을 때,
배열을 순회하면서 target을 찾으면 true,
찾지 못했다면 false를 반환하는 함수

func linearSearch(arr: [Int], target: Int) -> Bool {
    for i in 0..<arr.count {
        if arr[i] == target {
            return true
        }
    }
    return false
}
let arr = [6, 2, 42, 17, 9, 23]
print(linearSearch(arr: arr, target: 23))
// true