이진탐색

오름차순으로 정렬되어 있는 리스트(배열)에서 찾고자 하는 원소 item 의 위치를 찾을 때, 리스트(배열)에서 중간지점을 구한 후, item 값과 비교하여, item 값이 중간지점보다 작으면, 왼쪽부분에서 다시 중간지점을 찾아서 비교하여, 탐색하고, 크면 오른쪽부분에서 탐색한다. 중간지점과 item 과 값이 같으면 인덱스를 반환한다.

Pseudo-code

Algorithm binarySearch(A, item, n)
    left = 0 
    right = n-1 
    while (left <= right)  
       mid = (left + right) / 2   
       if (x == A[mid]) then
           return mid
       else if (x < A[mid])
           right = mid – 1
       else 
           left = mid + 1

Python

def binarySearch(arr, key):
    left = 0
    right = len(arr) - 1
    while (left <= right):
        mid = (left + right) // 2
        if key == arr[mid]:
            return mid
        elif key > arr[mid]:
            left = mid + 1
        elif key < arr[mid]:
            right = mid - 1

Java

public class BinarySearch{
    public void search(int key, int[] arr){
        int left = 0;
        int right = arr.length - 1;
        int mid;

        while(left <= right){
             mid = (left + right) / 2;
            if(key == arr[mid]){
                return mid;
            }
            if(key > arr[mid]){
                left = mid + 1 
            }
            else{
                right = mid - 1
            }

        }
    }
}

수행시간분석

T(n) = k + 1

n * (1/2)^k = 1
k = log n 일때

T(n) = log n + 1

T(n) = O(log n)

이진탐색 - 분할과 정복

분할과 정복의 방법으로 재귀적으로 표현

Pseudo-code

Algorithm binarySearch(A, item, left, right)
    if left > right
        return -1 : item이 없을 경우 -1 반환
    else
        mid = (left + right) / 2 : 2로 나눈 몫을 구하는 연산
        if (item == A[mid])
            return mid
        else if (item < A[mid])
            return binarySearch(A, left, mid-1) 
        else
            return binarySearch(A, mid+1, right)

Python

def binarySearch(arr, item, left, right):
    if left > right:
        return -1
    else:
        mid = (left + right)//2
        if item == arr[mid]:
            return mid
        elif item < arr[mid]:
            return binarySearch(arr, item, left, mid-1)
        else:
            return binarySearch(arr, item, mid+1, right)

Java

public class BinarySearch{
    public void binarySearch(int[] arr, int key, int left, int right){
        int left = 0;
        int right = arr.length - 1;
        int mid;

        while(left <= right){
             mid = (left + right) / 2;
            if(key == arr[mid]){
                return mid;
            }
            if(key > arr[mid]){
                return binarySearch(arr, key, mid + 1, right)
            }
            else{
                return binarySearch(arr, key, left, mid - 1)
            }

        }
    }
}

수행시간

T(n) = 0 (if n = 1)

<= T(n/2) + 1 (if n > 1)

T(n) <= T(n/2) + 1 <= [T(n/2^2) + 1] + 1

<= T(n/2^2) + 2 <= [T(n/2^3) + 1] + 2

<= T(n/2^3) + 3 <= [T(n/2^4) + 1] + 3

…

<= T(n/2k) + k

n/2k = 1
k = log n 일 때,

<= T(1) + log n

T(n) = O(log n)