4. 탐색 알고리즘(순차, 이진 탐색)

개념

• 순차 탐색: 데이터를 찾기 위해 앞에서부터 데이터를 확인하는 방법
  • 시간 복잡도: O(N)
• 이진 탐색: 정렬되어 있는 리스트의 탐색 범위를 절반씩 좁혀가며 탐색하는 방법
  • 즉, 시작점 + 끝점 + 중간점을 설정을 해줘야함
  • 시간 복잡도: O(logN)

 

방법

    public static int binarySearch(int[] List, int target, int start, int end){
        int mid;

        int result = -1;
        while(start <= end){
            mid = (start + end) / 2;
            
            if(List[mid] == target){
                result = List[mid];
                break;
            } else if (List[mid] < target) {
                end = mid - 1;
            } else{
                start = mid + 1;
            }
        }

        return result;
    }

 

만약 딱 떨어지는 수가 정답이 아니고 가장 최적의 값을 찾는것 이라면, result값을 계속 기록해줘야함

예시) target 값에 가장 가까운 큰 값을 찾는 경우

    public static int binarySearch(int[] List, int target, int start, int end){
        int mid;

        int result = -1;
        while(start <= end){
            mid = (start + end) / 2;
            
            if(List[mid] == target){
                result = List[mid];
                break;
            } else if (List[mid] < target) {
                end = mid - 1;
            } else{
                result = List[mid]; //result에 기록
                start = mid + 1;
            }
        }

        return result;
    }

 

 

 

파라메트릭 서치(Parametric Search)

• 정의: 최적화 문제를 결정 문제(예 or 아니오)로 바꾸어 해결하는 기법
  • 특정 범위에서 특정 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
  • 해당 유형은 이진 탐색을 이용하여 효과적으로 해결 가능