이진 탐색

정의

정렬되어 있는(이분 탐색의 주요 조건) 배열에서 데이터를 찾으려 시도할 때, 
순차탐색처럼 처음부터 끝까지 하나씩 모든 데이터를 체크하여 값을 찾는 것이 아니라
탐색 범위를 절반씩 줄여가며 찾아가는 탐색 방법이다.

 

시간 복잡도

• 전체 탐색 : O(N)
• 이분 탐색 : O(logN)

 

 

동작 과정

1. 우선 정렬을 한다.
2. left와 right로 mid 값을 설정한다.
3. mid와 내가 구하고자 하는 값과 비교한다.
4. 구할 값이 mid보다 :left = mid + 1 구할 값이 mid보다 낮으면 :right = mid - 1
5. left > right가 될 때까지 계속 반복하기

 

 

소스 코드

Java

public static int solution(int[] arr, int M) { // arr 배열에서 M을 찾자
	
    Arrays.sort(arr); // 정렬
	
    int start = 0;
    int end = arr.length - 1;
    int mid = 0;

    while (start <= end) {
        mid = (start + end) / 2;
        if (M == arr[mid]) {
            return mid;
        }else if (arr[mid] < M) {
            start = mid + 1;
        }else if (M < arr[mid]) {
            end = mid - 1;
        }
    }
    throw new NoSuchElementException("타겟 존재하지 않음");
}

Python

def binary_search(target, data):
    data.sort()
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2
        if data[mid] == target:
            return mid 
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid -1

    return None

 

 

 

 

 

 

 

 

출처:
https://gyoogle.dev/blog/algorithm/Binary%20Search.html