이진탐색 알고리즘

순차탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

 

이진탐색

정렬되어 있는 리스트에서 탐색범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 

-> 시작점, 끝점,중간점을 이용하여 탐색범위 설정 

이진탐색은 탐색범위를 절반씩 줄이며, 시간복잡도는 O(logN)이다. 

 

결론적으로 큰 탐색범위를 보면 가장 먼저 이진탐색을 떠올려야 한다.(선형탐색을 할 경우 시간복잡도 커짐)

중간점의 값은 시간이 지날수록 최적화된 값이 된다. 

 

++) 파라매트릭 서치

= 최적화 문제를 결정 문제(예/아니요)로 바꾸어 해결하는 기법.

예시) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제

파라메트릭 서치도 이진 탐색을 통해 해결가능하다.

 

이진탐색 과정 

 

1부터 11까지의 카드가 있다. 여기서 4를 찾는 방법을 이진탐색을 통해 알아보자.

 

 

시작값을 1, 끝값을 11로 두자 그러면 중간값은 6이된다.

중간값(6)보다 찾고자 하는 값(4)가 작기 때문에 end값을 middle-1로 줄여준다.

 

그러면 처음값(1) 부터 끝값(5)의 중간값은 3이다.

중간값(3)보다 찾고자하는 값 (4)이 더 크기 때문에

시작값=middle+1로 잡아준다.

 

그러면 시작값:2 끝 값:5 가 된다. middle은 그대로 3이다. 소수점 떨어뜨려줘야한다.

중간값(3)보다 찾고자 하는값 (4)가 크기에 

시작값:middle+1로 맞춰준다. 그러면 시작값은 3 끝값은 5가 되고 중간값은 4가 된다.

 

이런 이분 탐색 과정을 자바 코드로 나타내보겠다.

(코드의 출처는 유튜브 "동빈나"님의 이진탐색 강의를 보고 복습하면서 따라쓴 코드입니다)

 

 
import java.util.Scanner;
 
public class Main2 {
    public static int binarySearch(int[] arr, int target, int start, int end) {
        while (start <= end) {
            int mid = (start + end) / 2;
 
            // 찾은 경우
            if (arr[mid] == target) {
                return mid;
                // 찾고자 하는 값이 중간값보다 작은경우
            } else if (arr[mid] > target) {
                end = mid - 1;
 
                // 찾고자 하는 값이 중간값보다 큰 경우
            } else {
                start = mid + 1;
            }
        }
 
        return -1;
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
        int target = sc.nextInt();
        
        int []arr=new int[n];
        
        for(int i=0;i<n;i++) {
            arr[i]=sc.nextInt();
        }
        
        int result=binarySearch(arr,target,0,n-1);
        
        if(result==-1) {
            System.out.println("원소가 존재하지 않습니다.");'
        }
        else {
            System.out.println(result+1);
        }
    }
}

 

https://www.youtube.com/watch?v=94RC-DsGMLo&t=530s 

이진탐색 예제

 

나무꾼 철수가 나무를 잘라야한다. 철수는 절단기로 나무를 자르고, 절단기로 자를 때는 모두 일정한 길이로 잘라지게 된다. 나무는 총 4그루가 있는데 20m,15m,10m,17m가 있다. 적어도 7m의 나무를 자르기 위해 철수는 나무를 최대 몇m 잘라낼 수 있을까?

(문제출처: 백준 2805번 나무자르기)

https://we1cometomeanings.tistory.com/227

[java 백준] 실버 3/ 2805번 나무자르기

 

초기값을 0으로 두고, 가장 끝 값을 20으로 두자. (20이 이 중 가장 큰 값이기 때문)

그러면 중간 값 10을 일정한 길이로 두고 자르면

10 + 5 +0+7 =22 이기에 우리가 원하는 7 m보다 크다. 우선 이 값을 keep해둔다. 우리가 원하는 길이보다 middle이 10일때는 컸기 때문에 값의 범위를 좁혀주기 위해 시작값을 middle+1로 두고 끝값은 그대로 간다.

 

 

그러면 시작값 11 부터 끝값 20까지의 범위에서 중간값은 15가된다.

 

 

 

이때 남는 나무의 길이는 5+0+2 =7 이 된다. 우리가 원하는 7이 나왔다. 하지만 아직 초기값>끝값의 상황이 아니기때문에 계속 탐색을 진행한다. 

 

 

나무의 길이를 또한번 짧게 잘라주기 위해 middle+1을 시작값으로 잡고, 끝값은 그대로 간다. 그러면 시작값: 16 끝값은 20이고 중간값은 18이 된다.

 

 

이러면 2만 남기때문에 마지노 7보다 작기에 나무의 길이를 길게 늘려줘야한다. 이때 끝값을 middle-1로 둔다.

그러면 시작값은 16 끝값은 17이 된다. 

 

시작값이 16이고 끝값이 17이면 중간값은 16이다.

 

이때는 4+ 1=5 이기 때문에 7보다 작으므로 나무의 길이를 늘려줘야 한다. 그래서 끝값을 middle-1로 잡으면 15인데

 

시작값(16)>끝값(15)이기 때문에 이진탐색이 끝난다. 

 

 

이진탐색을 사용한 문제

-> 길이 자르기 

--> 정렬된 배열에서 특정수의 개수 구하기 (특정 값이 등장하는 첫번째 위치와 마지막 위치를 찾아 위치 차이를 계산해 문제 해결 가능)

 

 

이진탐색 라이브러리 

파이썬의 이진탐색 라이브러리

bisect_left(a,x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환

bisect_right(a,x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스 반환

 

bisect_left 는 C++ lower bound

bisect_right는 C++의 upper bound

 

upperbound는 찾고자 하는 특정값을 초과하는 첫 위치를 반환하고,

lowerbound는 특정 값 이상인 첫 위치를 반환한다.