2일차 정리(Arrays.binarySearch에 의한 이진 검색, 자연정렬)

1. Arrays.binarySearch에 의한 이진 검색

Java는 배열에서 이진 검색을 하는 메서드를 표준 라이브러리로 제공합니다.

이진 검색 표준 라이브러리의 메서드로는 java.util.Arrays 클래스의 binarySearch 메서드가 있습니다.

binarySearch 메서드는 다음고 ㅏ같은 장점이 있습니다.

1) 이진 검색 메서드를 직접 코딩할 필요가 없다.

2) 모든 자료형 배열에서 검색할 수 있다.

링크 : https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html

Modifier and Type	Method and Description
static int	binarySearch(byte[] a, byte key) Searches the specified array of bytes for the specified value using the binary search algorithm.
static int	binarySearch(byte[] a, int fromIndex, int toIndex, byte key) Searches a range of the specified array of bytes for the specified value using the binary search algorithm.
static int	binarySearch(char[] a, char key) Searches the specified array of chars for the specified value using the binary search algorithm.
static int	binarySearch(char[] a, int fromIndex, int toIndex, char key) Searches a range of the specified array of chars for the specified value using the binary search algorithm.
static int	binarySearch(double[] a, double key) Searches the specified array of doubles for the specified value using the binary search algorithm.
static int	binarySearch(double[] a, int fromIndex, int toIndex, double key) Searches a range of the specified array of doubles for the specified value using the binary search algorithm.
static int	binarySearch(float[] a, float key) Searches the specified array of floats for the specified value using the binary search algorithm.
static int	binarySearch(float[] a, int fromIndex, int toIndex, float key) Searches a range of the specified array of floats for the specified value using the binary search algorithm.
static int	binarySearch(int[] a, int key) Searches the specified array of ints for the specified value using the binary search algorithm.
static int	binarySearch(int[] a, int fromIndex, int toIndex, int key) Searches a range of the specified array of ints for the specified value using the binary search algorithm.
static int	binarySearch(long[] a, int fromIndex, int toIndex, long key) Searches a range of the specified array of longs for the specified value using the binary search algorithm.
static int	binarySearch(long[] a, long key) Searches the specified array of longs for the specified value using the binary search algorithm.
static int	binarySearch(Object[] a, int fromIndex, int toIndex, Object key) Searches a range of the specified array for the specified object using the binary search algorithm.
static int	binarySearch(Object[] a, Object key) Searches the specified array for the specified object using the binary search algorithm.
static int	binarySearch(short[] a, int fromIndex, int toIndex, short key) Searches a range of the specified array of shorts for the specified value using the binary search algorithm.
static int	binarySearch(short[] a, short key) Searches the specified array of shorts for the specified value using the binary search algorithm.
static <T> int	binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c) Searches a range of the specified array for the specified object using the binary search algorithm.
static <T> int	binarySearch(T[] a, T key, Comparator<? sper T> c) Searches the specified array for the specified object using the binary search algorithm.

- 기본 자료형 배열에서 binarySearch메서드로 검색하기

---

※ Java 메서드의 종류는 다음과 같이 두 가지 입니다.

 가. 인스턴스 메서드(비정적 메서드) : static를 붙이지 않고 선언한 메서드

 나. 클래스 메서드(정적 메서드) : static를 붙여 선언한 메서드

 차이점 : 메서드가 인스턴스에 포함되는지의 여부

- 코드

 인스턴스 메서드 호출 시 : 클래스형 변수 이름.메서드 이름

 클래스 메서드 호출 시 : 클래스 이름.메서드 이름

- binarySearch(Object[] a, Object key) : 자연 정렬이라는 방법으로 요소의 대소 관계를 판단합니다. 따라서 정수 배열, 문자열 배열에서 검색할 때 적당합니다.

- binarySearch(T[] a, T key, Comparator<? sper T> c) : "자연 순서"가 아닌 순서로 줄지어 있는 배열에서 검색하거나 "자연 순서"를 논리적으로 갖지 않는 클래스 배열에서 검색할 때 알맞습니다.

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

- 자연 정렬(natural ordering)

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

문자열 정렬	자연 정렬
텍스트1.txt	텍스트1.txt
텍스트10.txt	텍스트2.txt
텍스트100.txt	텍스트3.txt
텍스트2.txt	텍스트10.txt
텍스트3.txt	텍스트100.txt

- 자연 정렬로 정렬되지 않은 배열에서 검색하기

: 자연 정렬로 정렬되지 않은 배열에서의 검색은 제네릭 메서드(generic method)로 하면된다.

제너릭 메서드의 첫 번째 매개변수는 검색대상, 두번쨰 매개변수 키 값이다.

제너릭 메서드는 자료형에 구애받지 않는다. 따라서 매개변수로 전달하는 자료형은 Integer, String, 사용자정의 클래스등 어떤 것을 전달해도 좋다.

하지만 배열의 요소가 어떤 수서로 줄지어 있는지, 각 요소의 대소 관계를 어떻게 판단할 것인지에 대해서는 binarySearch 메서드에 알려주어야 한다. 이 정보는 세 번째 매개변수에 전달된다.

binarySearch(T[] a, T key, Comparator<? sper T> c)

- binarySearch 메서드 활용

- 제너릭 메서드(generic method) 활용

: 제너릭은 처리해야 할 대상의 자료형에 의존하지 않는 클래스(인터페이스)구현 방식입니다.

또한 Java에서 지원한 기능이므로 안전한 방법으로 사용할 수 있습니다.

제네릭 클래스는 클래스 이름 바로 뒤에 <Type> 같은 형식의 파라미터를 붙여 선언합니다.

※ 파라미터 이름을 작성하는 방법

1) 1개의 대문자를 사용합니다(소문자는 가급적 사용하지 않습니다.)

2) 컬렉션(collection)의 자료형은 element의 앞글자인 E를 사용합니다.

3) 맵(Map)의 키(key), 값(value)은 key와 value의 앞글자인 K와 V를 사용합니다.

4) 일반적으로 T를 사용합니다.

또한 형변수에는 와일드카드를 지정하는것도 가능