데이터 구조 - 이분법 찾기

1, 2 분 검색 (바 이 너 리 검색)    2 분 검색 은 절반 검색 이 라 고도 부 르 는데 효율 이 높 은 검색 방법 이다.    2 분 검색 요구: 선형 표 는 질서 표, 즉 표 의 결점 은 키워드 에 따라 질서 가 있 고 벡터 를 표 의 저장 구조 로 해 야 한다.차례 표를 설치 하 는 것 은 점차 질서 가 있 는 것 이다.
2. 이분 검색 의 기본 사상    2 분 검색 의 기본 사상 은 다음 과 같다. (R [low.. high] 는 현재 검색 구간 이다.) (1) 우선 이 구간 의 중점 위 치 를 확정한다.                   (2) 그 다음 에 조사 할 K 값 을 R [mid]. key 와 비교 합 니 다. 같 으 면 성공 적 으로 찾 아 이 위치 로 돌아 갑 니 다. 그렇지 않 으 면 새로운 검색 구간 을 확인 하고 2 분 동안 계속 찾 아야 합 니 다. 구체 적 인 방법 은 다음 과 같 습 니 다.   ① R [mid]. key > K 의 경우 표 의 질서 성 을 통 해 알 수 있 듯 이 R [mid. n]. keys 는 모두 K 보다 크기 때문에 표 에 키워드 가 K 와 같은 결점 이 존재 한다 면 이 결점 은 반드시 위치 mid 왼쪽 의 하위 표 R [1. mid - 1] 에 있 기 때문에 새로운 검색 구간 은 왼쪽 표 R [1. mid - 1] 이다.    ② 유사 하 게 R [mid]. key    따라서 초기 검색 구간 R [1. n] 부터 현재 검색 구간 의 중점 위치 에 있 는 결점 키워드 와 비교 할 때마다 검색 성공 여 부 를 확인 할 수 있 으 며, 성공 하지 않 으 면 현재 검색 구간 이 절반 으로 줄어든다.이 과정 은 키워드 가 K 인 결점 을 찾 거나 현재 검색 구간 이 비어 있 을 때 까지 반복 된다.
 
 
public static int binarySearch(int[] a, int key) {
2:         int low = 0;
3:         int high = a.length - 1;
4: 
5:         while (low <= high) {
6:             int mid = (low + high) / 2;
7:             int midVal = a[mid];
8:
9:             if (midVal < key)
10:                 low = mid + 1;
11:             else if (midVal > key)
12:                 high = mid - 1;
13:             else
14:                 return mid;    // key found
15:         }
16:         return -(low + 1);     // key not found.
17:     }

이미
0 명 댓 글 달 고 강 타 - >
여기 < - 토론 참여
ITeye 추천
4. 567917. - 소프트웨어 인 재 는 언어 저 담 보 를 면제 하고 미국 에 가서 유급 으로 대학원 에 다 닙 니 다! -

좋은 웹페이지 즐겨찾기