Java Binarysort

03.04.2019 — Java, Algorithm — 1 min read

Java 이진탐색 구현하기

처음 입사하자마자 이진탐색을 구현해오라는 과제를 받았다.

구현은 둘째치고 이진탐색을 정보처리기사 공부할 때 잠깐 읽어본 것 외에는 알지못했기에 대혼돈에 빠졌다......

그래서 이포스트에서는 ArrayList로 이진탐색을 구현하는 법을 얘기하고자 한다.

구현해야 하는 것은 두가지였다.

이진탐색을 이용하여 오름차순, 내림차순 정렬로 값을 insert하는 함수 만들기
이진참색을 이용하여 값을 찾는 함수 만들기

첫번째 함수보다 두번째 함수가 구현하기 더 간단하다. 우선 이진탐색에서 값을 찾는 함수를 만드려면 값을 찾으려는 대상이오름차순, 혹은 내림차순으로 정렬되어있다는 조건이 필요하다.

값을 찾는 방법을 그림으로 설명하자면 우선 이와 같은 배열이 있다고 생각해보도록 하자.

오름차순으로 정렬되있는 size 6의 배열이 있다. 여기서 5의 index 값을 찾는 것이다.

우선 이 배열을 반으로 나눈 뒤 그 index에 들어있는 값을 가져온다

이 배열에서 총 index는 5이므로 5/2 = 2.5 (소수점 이하 값은 버린다)

즉, index 2 에 들어 있는 값을 가져온다.

index 2에 들어잇는 값은 3이다. 이 값을 찾으려는 값 5와 비교한다.

찾으려는 값 5보다 index 2의 값이 더 작으므로 반으로 자른 배열에서 왼쪽에 해당하는 배열은 더이상 찾지 않는다.

마치 up down 게임 처럼 찾으려는 값보다 가져온 값이 더작으면 up으로 찾고, 작으면 down으로 찾는다.

왼쪽을 제외한 배열에서 또 다시 반으로 index를 잘라 비교한다.

이를 코드로 구현하기 위해서 배열의 처음 index를 이 전에 반으로 자른 index에 1을 더해 계산한다.

3(2:이전에서 반으로 나눈 index 값 + 1)과 배열의 맨 끝 index 5를 더해 반으로 나눈다.

그러면 8/2 = 4 index 4의 값을 가져와 비교하게 된다.

index 4의 값은 우리가 찾으려던 값인 5이므로 이 함수가 끝나게 된다.

1public int findBinarySearchData(boolean asc, ArrayList<Integer> alNumber, int number) {
2        int result = -1;
3        int sourcekey = -1, targetkey = -1;
4        sourcekey = number;
5
6        boolean bFound = false;
7        int low = 0;
8        int high = alNumber.size() - 1;
9        int mid = -1;
10
11        // binary search
12        while (low <= high) {
13            mid = (low + high) / 2;
14            targetkey = alNumber.get(mid);
15                // ascending
16                if(asc) {
17                    if(sourcekey == targetkey) {
18                        bFound = true;
19                        break;
20                    }
21                    else if(targetkey > sourcekey) {
22                        high = mid - 1;
23                    }
24                    else {
25                        low = mid + 1;
26                    }
27                }
28                // descending
29                else {
30                    if(sourcekey == targetkey) {
31                        bFound = true;
32                        break;
33                    }
34                    else if(targetkey < sourcekey) {
35                        high = mid - 1;
36                    }
37                    else {
38                        low = mid + 1;
39                    }
40                }
41            }
42    
43            if(bFound) {
44                result = mid;
45            }
46    
47            return result;
48        }