데이터 구조 - 이분법 찾기
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. - 소프트웨어 인 재 는 언어 저 담 보 를 면제 하고 미국 에 가서 유급 으로 대학원 에 다 닙 니 다! -
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.