[자바 Do It! 알고리즘]Chapter03 검색 알고리즘(객체배열 검색, 자연정렬 배열 검색)

[객체의 배열에서 검색하기]

​

static int binarySearch(Object[] a, Object key)

1. 자연정렬이라는 방법으로 요소의 대소 관계를 판단합니다. 따라서 정수 배열, 문자열 배열에서 검색할 때 적당합니다.

​

static<T> int binarySearch(T[] a, T key, Comparator<? super T> c)

1. "자연 순서"가 아닌 순서로 줄지어 있는 배열에서 검색하거나 "자연 순서"를 논리적으로 갖지 않는 클래스 배열에서 검색할 때 알맞습니다.

​

※ 자연 정렬(natural ordering)

1. binarySearch 메서드에 배열과 키 값을 전달하는 방법으로 검색할 수 있는 이유는 String 클래스가 Comparable<T> 인터페이스와 compareTo 메서드를 구현하고 있기 때문입니다.

문자열 정렬	자연 정렬
텍스트 1.txt	텍스트 1.txt
텍스트 10.txt	텍스트 2.txt
텍스트 100.txt	텍스트 10.txt
텍스트 2.txt	텍스트 21.txt
텍스트 21.txt()	텍스트 100.txt

2. 둘 다 '정렬이 되었다'라는 사실에는 문제가 없습니다.

3. 하지만, 문자열 정렬은 말 그대로 자연스럽지 않습니다. 컴퓨터의 문자열 정렬은 동일한 위치에 있는 문자의 대소 비교를 통해 정렬하기 때문에 왼쪽과 같은 결과가 나옵니다.

4. 하지만 사람에게는 오른쪽 형태의 정렬이 더 자연스럽니다. 바로 이 정렬을 '자연 정렬'이라고 부릅니다.

​

자연 정렬로 정렬된 배열에서 검색하기

​

자연스러운 순서로 정렬할 필요가 있을 때 클래스 정의법