이진탐색(Binary Search)을 활용해 효율적으로 서치하기

http://jjjayyy.tistory.com/47

여기서 이중 for문으로 정렬된 두 데이터의 같은 값을 추출하는 작업을 진행했다.

하지만 디버깅을 해보니 같은 값이 없을 때에도 해당 리스트의 전체를 돌며 탐색해서 비효율적이었다.

가령, List A의 size는 (20)이고 List B의 size는 (5000)이라면

같은 값이 없는 조건일 경우 한 번씩 다 확인하면서 총 100,000번 비교해보는 셈이다.

그러다 지하철을 오며가며 본 알고리즘에서 이진탐색이 생각나서 적용해봤다.

for(ItemVO listVo : list) {
 
                    int mid = 0;
                    int first = 0;
                    int last = newItemList.size() - 1;
 
                    while(first <= last) {
 
                        mid = (first + last) / 2;
 
                        if(listVo.getSeq().equals(newItemList.get(mid).getSeq())) {
                            listVo.setItemNm(newItemList.get(mid).getItemNm());
                            listVo.setPrice(newItemList.get(mid).getPrice());
                            break;
                        } else {
                            if(Integer.parseInt(listVo.getSeq()) < Integer.parseInt(newItemList.get(mid).getSeq())) {
                                last = mid - 1;
                            } else {
                                first = mid + 1;
                            }
                        }
                    }
                }

구글에 '이진탐색 자바' 라고만 쳐도 훨씬 더 좋은 정보들이 주루룩 나오므로 내가 적용한 코드만 올려야겠다.

DB에 varchar로 저장되어 있는 Seq(시퀀스)를 int 형식으로 만들어 주었다.

만들면서 주의할 부분은

- mid = first + last / 2

: 이렇게 괄호를 빼고 진행했더니 last를 2로 먼저 나눠서 이상하게 탐색을 진행했다.

  꼭, (first + last) / 2  괄호를 붙여주자!

- 불러오는 데이터의 정렬 순서가 DESC

: 해당 리스트는 DB에서 정렬해서 불러온건데, SELECT * FROM ITEM ORDER BY SEQ DESC 이런식으로 되어있었다.

  하지만 위의 while문을 빠져나오려면 ASC로 오름차순 정렬을 해주어야한다.

  정 내림차순으로 진행하고자 한다면 while(first >= last) 로 바꾸면 되지 않을까 생각한다.

-------------------------------- 19.01.07 추가 --------------------------------

import java.util.ArrayList;
import java.util.List;
 
public class TimeTest {
 
    public static void main(String[] args) {
 
        //시작시간
        long start = System.currentTimeMillis();
 
        int cnt = 0;
 
        List<Integer> arr = new ArrayList<>();
        List<Integer> tempArr = new ArrayList<>();
 
        for(int i=0; i<100000; i++) {
            arr.add(i);
        }
 
        for(int i=0; i<40000; i++) {
            tempArr.add(i*2);
        }
 
        //이진탐색 (cnt : 64 / 0.031sec)
        for(int i=0; i<arr.size(); i++) {
 
            int mid = 0;
            int first = 0;
            int last = tempArr.size() - 1;
 
            while(first <= last) {
 
                mid = (first + last) / 2;
 
                if(arr.get(i) == tempArr.get(mid)) {
                    cnt++;
                    break;
                } else {
                    if(arr.get(i) < tempArr.get(mid)) {
                        last = mid - 1;
                    } else {
                        first = mid + 1;
                    }
                }
            }
        }
 
        //이중 for문 (cnt : 64 / 7.945sec)
 
        int index = 0;
 
        Loop1 : for(int i=0; i<tempArr.size(); i++) {
 
            for(int j=index; j<arr.size(); j++) {
                if(tempArr.get(i) == arr.get(j)) {
                    index = j+1;
                    cnt++;
                    continue Loop1;
 
                }
            }
        }
 
        System.out.println(cnt);
 
        // 종료 시간
        long end = System.currentTimeMillis();
 
        System.out.println( "실행 시간 : " + ( end - start )/1000.0 );
    }
}

이진탐색과 이중 for문 탐색의 속도 차이가 급 궁금해서 비교해본거 추가