검색

배열 검색

1. 선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행합니다.
2. 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행합니다.
3. 해시법 : 추가 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행합니다.
   1. 체인법 : 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법
   2. 오픈 주소법 : 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법

---

선형 검색

순서대로 검색

import java.io.IOException;
import java.util.Arrays;


public class Main {
	public static void main(String[] args) throws IOException{
		int[] a = {1,2,3,4,5};
		int b = 5;
		System.out.println(seqSearch(a, a.length, b));
	}
	static int seqSearch(int[] a, int n, int key) {
		for (int i=0; i<n; i++) {
			if (a[i] == key)
				return a[i];
		}
		return -1;
	}
}

보초법

import java.io.IOException;
import java.util.Arrays;


public class Main {
	public static void main(String[] args) throws IOException{
		int[] a = {1,2,3,4,5,0};
		int b = 5;
		System.out.println(seqSearch(a, a.length-1, b));
	}
	static int seqSearch(int[] a, int n, int key) {
		int j = 0;
		 a[n] = key; // 보초를 추가
		while(true) {
			if (a[j] == key)
				break;
			j++;
		}
		return j == n ? -1 : a[j];
	}
}

선형 검색의 종료 조건

1. 검색할 값을 발견하지 못 하고 배열의 끝을 지나간 경우
2. 검색할 값과 같은 요소를 발견한 경우

보초법은 요소의 마지막 뒤에 검색할 값과 같은 요소를 넣어놓고

보초에 닿으면 종료한다.

이렇게 하면 원하는 키 값을 찾지 못했을 때 판단하는 종료 조건이 없어도 된다.

---

이진 검색

요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘

import java.io.IOException;
import java.util.Arrays;


public class Main {
	public static void main(String[] args) throws IOException{
		int []a = {5,4,2,5,6,2,5,7,8,9,0};
		System.out.println(binSearch(a, a.length, 9));
	}
	static int binSearch(int[] a, int n, int key) {
		int pl = 0;
		int pr = n - 1;
		
		do {
			int pc = (pl + pr) / 2;
			if (a[pc] == key)
				return pc;
			else if (a[pc] < key)
				pl = pc + 1;
			else
				pr = pc - 1;
		} while(pl <= pr);
		return -1; //검색 실패
	}
}

 

Arrays.binarySearch(요소, key) : 이진 검색 메소드

 

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

자연 순서가 아닌 순서로 줄지어 있는 배열에서 검색하거나

자연 순서를 논리적으로 갖지 않는 클래스 배열에서 검색할 때 쓰임

 

자연 정렬

사람에게 보기 편한 정렬

문자열 정렬

1. 텍스트1
2. 텍스트10
3. 텍스트100
4. 텍스트2

자연 정렬

1. 텍스트1
2. 텍스트2
3. 텍스트10
4. 텍스트100

---

Java 메서드의 종류

1. 인스턴스 메서드(비정적 메소드)
   1. static을 붙이지 않고 선언
2. 클래스 메서드(정적 메서드)
   1. static을 붙여 선언함
   2. 클래스 전체에 대한 처리를 담당
   3. 인스턴스 메서드와 처리 영역을 구분하기 위해 사용

---

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

• 제너릭 메서드를 이용한다.
• 제너릭 메서드의 첫 번째 매개변수 a는 검색 대상이고, 두 번째 매개변수 key는 키 값이다.
• 제너릭 메서드는 자료형에 구애받지 않는다.
• 각 요소의 대소 관계를 어떻게 판단할 것인지에 대해 binarySearch 메서드에 알려주어야 한다. 이 정보는 세 번째 매개변수 c에 전달한다.

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

세 번째 매개변수 c에는 comparator를 전달한다.