'2018/01/18'에 해당되는 글 1건

  1. 2018.01.18 [JAVA] 이진검색(Binary Search) 구현하기

주어진 리스트가 정렬이 되어있다는 가정하에서는 

이진 검색(binary search)를 사용하는게 매우 효율적인 방법이란다.


소스를 보니 재귀호출을 사용하여 검색이 진행된다.

(JAVA 프로그래밍 면접 이렇게 준비한다 - 73P)



public class BinarySearch {

public static boolean binarySearch(final List<Integer> numbers, Integer value) {

if(numbers==null || numbers.isEmpty()) // 전달받은 numbers 리스트가 null이거나 비워져있는지 확인

return false;

Integer comparsion = numbers.get(numbers.size() / 2); //  리스트 크기 반띵하여 원소 위치의 값을 추출

if(value.equals(comparsion)) {   

return true;

}

if(value<comparsion) {

return binarySearch(numbers.subList(0, numbers.size() / 2), value);

} else {

return binarySearch(numbers.subList(numbers.size() / 2 + 1, numbers.size()), value);

}

}

public static void main(String[] args) {

List<Integer> list = new ArrayList<>();

list.add(1);

list.add(4);

list.add(5);

list.add(9);

list.add(14); // 정렬하기 귀찮아서 삽입할때 순서대로 삽입시켰다.



System.out.println(binarySearch(list, 9)); // 삽입된 리스트와, 찾고하자는 밸류값을 파라메터로 던진다.

}

}


소스가 어렵지 않아 쉽게 이해할 수 있었다.



Posted by 루우지