Binary Search - Recursive / Non-recursive

• 이진 탐색(Binary는 호남선 Search) : 가운데 element와 현재 찾고 있는 element의 비교를 통해 탐색 범위를 반씩 줄여나가는 탐색법
  • 가정 : Sorted array
• 재귀 알고리즘(수 찾기 문제)

public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {2,5,7,12,18,40,52,61,89,100,121};
        int result = binarysearch(arr, 7, 0, 10);
        System.out.println(result);
    }


    public static int binarysearch(int[] arr, int keyValue, int lowIndex, int highIndex) {
        if(lowIndex > highIndex) {
            return -1; //there is no keyValue in the given array
        }
        int midIndex = (lowIndex+highIndex)/2;
        if(arr[midIndex]>keyValue) {
            return binarysearch(arr, keyValue, lowIndex, midIndex-1);	
            // arr[lowIndex] x x keyValue x x arr[mid] x x x x x arr[high]
        }
        else if(arr[midIndex]<keyValue) {
            return binarysearch(arr, keyValue, midIndex+1, highIndex);	
            // a[l] x x x x x a[m] x x keyValue x x a[h]
        }
        else return midIndex;	// arr[midIndex] == keyValue
    }

}

 

• 비재귀 알고리즘(수 찾기 문제)

public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {2,5,7,12,18,40,52,61,89,100,121};
        int result = binarysearch(arr, 7);
        System.out.println(result);
    }


    public static int binarysearch(int[] arr, int keyValue) {
        int lowIndex = 0;
        int highIndex = arr.length;

        while (lowIndex <= highIndex) {
            int midIndex = (lowIndex + highIndex) / 2;

            if (arr[midIndex] > keyValue) {
                highIndex = midIndex - 1;    // arr[lowIndex] x x keyValue x x arr[mid] x x x x x arr[high]
            } else if (arr[midIndex] < keyValue) {
                lowIndex = midIndex + 1; // a[l] x x x x x a[m] x x keyValue x x a[h]
            } else return midIndex;    // arr[midIndex] == keyValue
        }
        return -1;
    }
}

 

• 시간복잡도 분석
  • $O(log n)$ : n개의 원소를 반으로 줄여 가며 가운데 원소를 확인하면 최악의 경우 log n번 확인해야 한다.