이진 탐색 (Binary Search) 알고리즘

이진탐색 알고리즘

• 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘
• 리스트의 중간 부분에 찾는 원소가 있는지 확인 후, 왼쪽에 있는지 오른쪽에 있는지 판단하여 검색
• 즉, 자료를 반으로 나누어 탐색하는 방법
• 시간복잡도 : O(logN)

예시

• 찾고자 하는 값을 찾을 때까지 과정 반복!
• 이진 탐색 알고리즘을 사용할때는 반드시 정렬된 자료에만 사용해야한다.

코드

public static int binarySearch(int arr[], int left, int right, int key) { //반복문
        
        while(left<right) {            
            int mid = (left+right)/2;
            if(key==arr[mid]) //탐색 성공
                return mid;
            else if(key>arr[mid]) //중간 원소보다 크면
                left = mid+1;
            else //중간 원소보다 작으면
                right = mid-1;
        }
        return -1;
}

public static int binarySearch(int arr[], int left, int right, int key) { //재귀문
        
        if(left>right) return -1;
        int mid = (left+right)/2;
        if(arr[mid]==key) //탐색 성공
            return mid;
        else if(key>arr[mid]) // 중간 원소보다 크면
            return binarySearch(arr,mid+1,right,key);
        else // 중간 원소보다 작으면
            return binarySearch(arr,left,mid-1,key);
}