검색 알고리즘.

검색 알고리즘은 우리가 일상 생활에서 가장 많이 사용하는 알고리즘입니다. 검색 알고리즘에는 두 가지 유형이 있습니다.

선형 검색

이진 검색

선형 검색.

가장 간단한 검색 알고리즘 중 하나입니다. 선형 검색 알고리즘은 일치하는 항목이 발견될 때까지 또는 목록의 끝까지 처음부터 끝까지 목록 또는 배열과 같은 값 시퀀스의 순회를 포함하는 순차적 알고리즘입니다. 검색이 성공하면, 즉 요소가 있는 경우 알고리즘은 요소의 인덱스를 반환하지만 요소를 찾을 수 없는 경우 알고리즘은 -1을 반환합니다.

선형 탐색 알고리즘의 특징.

선형 검색 알고리즘은 정렬된 목록과 정렬되지 않은 목록 모두에 적용할 수 있습니다.
선형 검색 알고리즘은 시간이 배열/목록의 크기에 선형적으로 의존함을 의미하는 O(N)의 시간 복잡도를 갖습니다.
구현이 매우 간단합니다.

선형 검색 알고리즘의 구현.

def linear_search(array, x, n):
    for i in range(0, n):
        if array[i] == x:
            return i
    return -1

#implementation
array =[23, 45, 12, 90, 34, 7]
x = 34
n = len(array)

result = linear_search(array, x, n)

if result == -1:
    print("Element is not present in the array!")

else:
    print("Element is present in the array !")

산출:

Element is present in the array !

이진 검색

선형 검색 알고리즘과 달리 이진 검색 알고리즘은 목록이나 배열의 요소가 정렬된 경우에만 사용할 수 있습니다.

이진 검색과 관련된 단계.

1단계. 먼저 해당 목록의 요소가 정렬되어 있는지 확인해야 합니다.

2단계. 그렇다면 배열/목록 중간에 있는 요소와 요소를 비교하십시오

.

3단계. 요소가 배열/목록 중간에 있는 요소와 일치하면 요소의 인덱스를 반환합니다.

4단계. 그렇지 않으면 찾고 있는 요소가 목록/배열 중간에 있는 요소보다 크거나 작은지 확인합니다.

5단계. 요소가 목록/배열의 중간에 있는 요소보다 크면 오른쪽에 있는 요소를 선택하고 1단계부터 다시 시작합니다.

6단계. 검색할 요소가 왼쪽 요소의 중간에 있는 요소보다 작으면 왼쪽에 있는 요소를 선택하고 1단계부터 다시 시작한다.

선형 검색 알고리즘과 달리 이진 검색 알고리즘은 목록/배열에 매우 큰 요소가 포함된 경우에 매우 유용합니다. 그러나 해당 목록/배열은 미리 정렬해야 합니다.

이진 검색 알고리즘의 특징.

매우 큰 목록/배열을 검색하는 데 특히 좋습니다.
O(Log N)의 시간 복잡도를 갖는다.
이진 검색은 두 가지 방법으로 구현할 수 있습니다.

반복 방법.

재귀 방법.
이진 검색을 구현하는 재귀적 방법은 분할 정복 접근 방식을 따르지만 반복적 방법은 그렇지 않습니다. 이 두 가지 방법 모두 아래와 같이 구현할 수 있습니다.

이진 검색의 반복적인 구현.

def binary_search(array, x, low, high):
    while low <= high:
        mid = low + (high - low)//2
        if array[mid] == x:
            return mid
        elif array[mid] < x:
            low = mid +1
        else:
            high = mid -1
    return -1

#implementation of the algorithm
array = [12, 13, 15, 17, 28, 88, 90, 99]
x = 28
index = binary_search(array, x, 0, len(array)-1)
if index != -1:
    print("Element can be found at Index: " +str(index))
else:
    print("Element cannot be found !")

산출:

Element can be found at Index: 4

이진 검색 알고리즘의 재귀적 구현.

def binary_search(array, x, low, high):
    if high >= low:
        mid = low + (high - low)//2
        if array[mid] == x:
            return mid
        elif array[mid] > x:
            return binary_search(array, x, low,  mid-1)
        else:
            return binary_search(array, x, mid + 1, high)

    return -1

#implementation of the algorithm
array = [12, 67, 77, 79, 88, 90]
x = 79
result_index = binary_search(array, x, 0, len(array)-1)
if result_index != -1:
    print("The element in the array can be found at index: " +str(result_index))
else:
    print("Element cannot be found in the array !")

산출:

The element in the array can be found at index: 3