이진 검색

소개

"검색"의 의미를 사전에서 찾고 싶다고 가정해 봅시다. 단어 하나하나를 처음부터 끝까지 읽고 "검색"이라는 단어를 찾는 방법은 어떤 방법을 선호합니까, 아니면 사전의 중간 페이지로 이동합니다. 중간 페이지의 단어가 "검색"이라는 단어보다 알파벳순으로 작은지 확인하고 이것이 사실이면 사전의 왼쪽 부분을 무시하고 사전의 오른쪽 부분에서 동일한 과정을 반복할 수 있습니다. 당연히 사전의 모든 단어를 읽는 데 시간이 많이 걸리고 두 번째 방법에서는 검색 영역이 줄어들기 때문에 누구나 두 번째 방법을 선택할 것입니다. 이 검색 방법을 이진 검색이라고 합니다. 이진 검색은 정렬된 배열에서 요소의 위치를 ​​찾기 위한 검색 알고리즘이며 배열은 오름차순 또는 내림차순으로 정렬할 수 있습니다.

# variables name we are going to use

# arry = [10,20,30,40,50,60,70,80,90,100] -> sorted array
# start = 0 -> starting position of the array
# end = len(arr)-1 -> ending position of the array
# mid = start + (end - start) // 2 -> mid of the array
# item = 80 -> we are searching index of 80

이진 검색에서는 주로 다음 단계를 수행합니다.

먼저 배열의 mid 위치를 찾은 다음 mid 위치에 있는 요소가 찾고 있는 item와 같은지 확인하고 그것이 사실이면 배열의 위치를 ​​반환합니다. 요소.

위의 조건이 충족되지 않으면 mid 위치의 요소가 찾고 있는 item보다 작은지 확인하고 그것이 사실이면 배열의 위쪽 절반에서 항목을 찾습니다. .

위의 조건이 충족되지 않으면, 즉 배열의 mid 위치에 있는 요소가 찾고 있는 항목보다 크고, 이것이 사실이면 배열의 아래쪽 절반에서 항목을 찾습니다.

요소를 찾을 때까지 이 작업을 계속 반복합니다. 그렇지 않으면 -1을 반환합니다

.

의사 코드 / 알고리즘

# step 1 variable initialization 

arr = [10,20,30,40,50,60,70,80,90,100] # -> sorted array
start = 0 # -> starting position of the array
end = len(arr)-1 # -> ending position of the array
mid = start + (end - start) // 2 # -> mid position of the array
item = 80 # -> we are searching index of 80

# step 2 Repeat step 3 while start <= end and arr[mid] != item
# step 3
mid = start + (end - start) // 2 
if arr[mid] < item:
    start = mid + 1
else:
    end = mid-1

# step 4 if the element at arr[mid] == item then we return the index of the item else we return -1

예시

arr = [10,20,30,40,50,60,70,80,90,100]가 있고 요소 80의 위치를 ​​찾아야 합니다. 먼저 일부 변수를 초기화합니다.

arr = [10,20,30,40,50,60,70,80,90,100] 
start = 0
end = len(arr)-1
mid = start + (end - start) // 2
item = 80 

여기에서 arr[mid]가 80보다 작다는 것을 알 수 있습니다. 즉, 50 < 80이므로 이제 배열의 아래쪽 절반을 무시하고 배열의 위쪽 절반에서만 검색할 수 있습니다

.

이제 배열의 위쪽 절반에서만 일부 검색을 수행해야 하므로 이것이 잘린 배열입니다.

여기서 시작 = 5, 끝 = 9 및 중간 = 7

이번에는 arr[mid] == 항목이므로 항목의 위치 즉 7을 반환할 것입니다. 이제 완전한 코드를 파이썬으로 작성해 보겠습니다.

이진 검색을 위한 Python 구현

def binarySearch(arr, x, i, j):
    while i <= j:
        mid = i + (j - i) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            i = mid + 1
        else:
            j = mid - 1
    return -1


# driver code
arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
x = 80
i = 0
j = len(arr) - 1
result = binarySearch(arr, x, i, j)
print("The Element is at position: ", result)

이진 검색의 JavaScript 구현

function binarySearch(arr, x) {
    while (i <= j) {
        let mid = Math.trunc(i + (j - i) / 2);
        if (arr[mid] === x) {
            return mid;
        } else if (arr[mid] < x) {
            i = mid + 1;
        } else {
            j = mid - 1;
        }
    }
    return -1;
}

const arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
const x = 80;
let i = 0;
let j = arr.length - 1;
const result = binarySearch(arr, x, i, j);
console.log("Searching element is present at the location:", result);

시간 복잡도

알다시피 각 배열의 비교 크기는 절반으로 줄어들므로 복잡도 방정식은 T(n) = T(n/2) + c 입니다. 따라서 최악의 경우 이진 검색의 시간 복잡도는

제한 사항

이진 검색은 약 100만 개의 요소 목록에서 요소를 검색하는 데 약 20번의 비교만 필요한 매우 효율적인 알고리즘이지만 다른 검색 알고리즘이 필요하지 않다는 의미는 아닙니다. 이진 검색 알고리즘을 사용하려면 목록을 정렬해야 하고 배열에 데이터를 저장하는 데 비용이 많이 듭니다.

결론

이 블로그에서는 여기까지입니다. 반복적 접근 방식을 사용하여 이진 검색을 설명하려고 시도했지만 나중에 재귀를 사용하여 최적화할 수 있습니다. 잘못된 부분이 있다고 생각되시면 댓글에 적어주시면 최대한 빨리 개선하도록 노력하겠습니다.