이진탐색(binary search)

먼저 이진 탐색을 위해서는 내부의 데이터가 정렬되어 있어야 한다.

 

이진 탐색을 위해서는 시작점 start, end, mid 를 이용하여 탐색한다

찾으려는 데이터와 중간점 위치의 데이터를  비교하며 반복하면서 데이터를 찾는다.

와 같은 과정으로 탐색해 나간다.

 

- python 코드

def binary_search(arr,goal,start,end):
    if start>end:
        return None
    mid = (start+end)//2
    if arr[mid]==goal:
        return mid
    elif arr[mid]>goal:
        return binary_search(arr,goal,start,mid-1)
    else:
        return binary_search(arr,goal,mid+1,end)

def binary_search(arr,goal,start,end):
    while start<=end:
        mid = (start+end)//2
        if arr[mid]==goal:
            return mid
        elif arr[mid]>goal:
            end = mid-1
        else:
            start = mid+1
    return None #결과 없음

-Java 코드

public class Main {
    public static int binarySearch(int[] arr, int start, int end, int goal) {
        if (start > end) return -1;

        int mid = (start + end) / 2; //or (start+end) >> 1;
        if (arr[mid] == goal)
            return mid;
        else if (arr[mid] > goal)
            return binarySearch(arr, start, mid - 1, goal);
        else
            return binarySearch(arr, mid + 1, end, goal);

    }

    public static int binarySearch2(int[] arr, int start, int end, int goal) {

        while (start <= end) {
            int mid = (start + end) / 2; //or (start+end) >> 1;
            if (arr[mid] == goal)
                return mid;
            else if (arr[mid] > goal)
                end = mid - 1;
            else
                start = mid + 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        int arr[] = {4,7,9,21,35,47,58,72};
        System.out.println(binarySearch(arr,0,arr.length-1,35));
        System.out.println(binarySearch2(arr,0,arr.length-1,35));
    }
}

 

이진탐색 코드는 구현이 까다로운 편으로 외우는 것이 좋다

 

[참고]

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

 

 

++) UpperBound, LowerBound 

이분 탐색시에 중복된 값이 있는 경우의 시작 위치와 마지막 위치를 리턴해준다

https://www.acmicpc.net/problem/1208,  https://www.acmicpc.net/problem/2143 과같은 문제에서 사용된다. 

1208번: 부분수열의 합 2

2143번: 두 배열의 합

중복된 값의 개수를 구할 수 있어서 이를 이용하는 경우에 사용 가능하다.  

private static int lowerBound(List<Integer> list, int goal) {
    int start = 0;
    int end = list.size();
    while (start < end) {
        int mid = (start + end) >> 1;
        if (list.get(mid) >= goal) end = mid;
        else start = mid + 1;
    }
    return end;
}

private static int upperBound(List<Integer> list, int goal) {
    int start = 0;
    int end = list.size();
    while (start < end) {
        int mid = (start + end) >> 1;
        if (list.get(mid) <= goal) start = mid + 1;
        else end = mid;
    }
    return end;
}