선형 검색

소개

길이가 n인 배열arr= [4,6,3,7,8,5,34,26,23]이 있고 이 배열에서 5에 대한 인덱스를 찾으려고 한다고 가정하면 가장 직관적인 검색 방법은 배열의 각 요소를 5와 비교하고 일치하는 경우 반환하는 것입니다. 인덱스 5, 요소 검색을 위해 배열을 순회하는 이 방법을 선형 검색 또는 순차 검색이라고 합니다.

다른 예를 들어보자

arr = [9,29,46,23,75,98] 
# find an index of 75
# desired output 4

75의 인덱스를 찾으려면 다음 단계를 따라야 합니다.

0부터 반복
len(arr)-1
arr의 각 요소를 비교합니다

.

일치하는 항목이 있으면 arr의 인덱스를 반환하고 요소가 배열에 없으면 -1을 반환합니다

.

파이썬 구현

def linearSearch(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

# driver code
arr =  [9,29,46,23,75,98]
x = 75
result = linearSearch(arr,x)
print("Elemen is present at Index ",result)

위의 코드에서 우리는 linearSearch 함수를 정의하고 있으며 검색할 두 개의 인수인 배열과 요소를 취합니다. 그런 다음 길이가 arr, 즉 6인 범위 함수로 for 루프를 실행하므로 최악의 경우 , 요소가 배열에 있으면 6번 반복합니다. 그런 다음 if 블록에서 i번째 인덱스의 요소가 검색하려는 요소와 같은지 확인하고 그것이 조건이면 요소의 인덱스를 반환합니다.

for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

# first iteration
if arr[0] == x: -> i.e 9 == 5 -> False
# second iteration
if arr[1] == x: -> i.e 29 == 5 -> False
# third iteration
if arr[2] == x: -> i.e 46 == 5 -> False
# fourth iteration
if arr[3] == x: -> i.e 23 == 5 -> False
#fifth iteration
if arr[4] == x: -> i.e 75 == 5 -> True
#our loop will stop here and it will return index 4

자바스크립트 구현

function linearSearch(arr, x) {
    for (let index = 0; index < arr.length; index++) {
        if (arr[index] === x) {
            return index;
        }
    }
    return -1;
}

// driver code
arr =[9,29,46,23,75,98];
x =  75;
result = linearSearch(arr, x);
console.log(result);

메모

동일한 요소가 두 번 이상 있으면 선형 검색은 첫 번째 요소의 인덱스를 반환합니다.

arr = [9,29,46,23,75,75,75,98] 
# here 75 is present at multiple index i.e index 4,5,6
# so the linear search will return index of only first element i.e 4

시간 복잡도

알고리즘의 최악의 경우는 전체 배열을 검색할 때 발생하며 요소가 배열에 존재하지 않는 경우 알고리즘은 f(n) = n + 1 비교를 수행하므로 최악의 경우 실행 시간 복잡도는 다음과 같습니다. 우리의 알고리즘은 n 즉 배열의 길이에 따라 달라집니다. 시간 복잡도 O(n)