1. 검색

---

• 데이터의 집합에서 원하는 값을 가진 요소를 찾아내는 것
• 특정 항목(key)에 주목
• key는 데이터의 일부
• Key를 찾는 조건은 하나만 지정하기도 하지만 논리곱/논리합을 사용하여 복합 지정 가능
• 데이터 집합에 대해 검색만 하는 경우 계산 시간이 짧은 것을 선택
• 검색 뿐 아니라 데이터 추가, 삭제 등을 자주 하는 경우 검색 이외의 작업에 소요되는 비용 고려
  -> 데이터 추가 비용이 많이 드는 경우?
  ex) 배열의 경우 중간에 추가하려면 뒤의 데이터들을 모두 뒤로 밀어 넣는 작업이 필요.
  -> 배열은 검색이 빠르지만 데이터를 추가하기 위한 비용이 많이 듦
  선택 알고리즘이 여러 가지인 경우 용도/목적, 실행 속도, 자료구조 등을 고려하여 선택

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

2. 선형 검색

---

• 요소가 직선으로 늘어선 배열에서 원하는 키 값을 만날 때 까지 맨 앞부터 순서대로 검색하는 것 - [ O(n) ]

• 배열 검색의 종료 조건
  1. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 -> 검색 실패
  2. 검색할 값과 같은 요소를 발견한 경우 -> 검색 성공
• 선형 검색은 배열에서 순서대로 검색하는 유일한 방법

• 보초법
  • 선형 검색은 반복할 때마다 종료 조건 1 , 2를 모두 판단
  • 이 비용을 50%로 줄이는 방법이 보초법
  • 검색하고자 하는 키 값을 맨 끝 요소에 추가해 저장(이 저장 값을 ‘보초’라고 함)
  • 항상 검색할 값이 배열에 존재하게 되므로 종료 조건 1을 판단할 필요가 없음

3. 이진 검색

---

• 요소가 오름차순(작은 값부터 큰 값으로) 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘
• 이진 검색을 한 단계 진행할 때마다 검색의 범위가 반으로 좁혀짐

검색에 성공하는 경우

• Arr[pc] < key : Arr[pl] ~ Arr[pc] 는 key보다 작으므로 검색 대상에서 제외함. 검색 범위는 Arr[pc+1] ~ Arr[pr]로 좁히고 pl 값을 pc+1로 업데이트(①->②)
• Arr[pc] > key : Arr[pc] ~ Arr[pr] 는 key보다 크므로 검색 대상에서 제외함. 검색 범위는 Arr[pl] ~ Arr[pc-1]로 좁히고 pr 값을 pc-1로 업데이트(②->③)

• 이진 검색의 종료 조건
  • Arr[pc]와 key가 일치하는 경우 -> 검색 성공
  • 검색 범위가 더 이상 없는 경우 -> 검색 실패

검색에 실패하는 경우

1. Arr[pc] 값(Arr[5])이 6 보다 크므로 pr=pc-1=4, 검색 범위를 Arr[0] ~ Arr[4] 로 줄임
2. Arr[pc] 값(Arr[2])이 6 보다 크므로 pr=pc-1=1, 검색 범위를 Arr[0] ~ Arr[1] 로 줄임
3. pc = 0+1/2 = 0 -> 중앙 요소 값 Arr[0]이 6 보다 작으므로 pl=pc+1=1, pl==pr이 됨
4. 중앙 요소 값 Arr[1]이 6보다 크므로 pr=pc-1=0 -> pr < pl 이 되면서 검색 불가

static int binSearch(int[] arr, int n, int key){ // a : 검색할 배열 
                                                // n : 배열 크기  key : 찾는 값
	int pl = 0; // 검색 범위 맨 앞 인덱스
	int pr = n-1; // 검색 범위 맨 끝 인덱스

	do{
	  int pc = (pl + pr) / 2; // 중앙 인덱스
	  if(arr[pc] == key) { return pc; } // 검색 성공
	  else if(arr[pc] < key) { pl = pc + 1; } // 검색 범위를 뒤쪽 반으로 좁히기
  	  else { pr = pc - 1; } // 검색 범위를 앞쪽 반으로 좁히기
	} while( pl <= pr ); // pr 이 pl보다 크거나 같을 때 까지만 검색이 가능
	  
	return -1; // 검색 실패
}

선형 검색의 평균 실행 횟수는 n/2로, O(n)으로 나타낸다.
이진 검색은 실행 할 때 마다 범위가 반으로 줄어들기 때문에 시간 복잡도는 O(log n) 이다

---

참고 도서

• Do it! 자바 프로그래밍 입문