하프 찾기 방법을 접기 :
정렬 된 테이블에서 검색 할 데이터 값을 검색 범위의 중간 요소 값으로 비교하면 세 가지 상황이 있습니다.
1) 발견되는 데이터 값이 중간 요소 값과 정확히 동일하면 중간 요소 값의 인덱스를 되돌려 놓으십시오.
2) 검색 할 데이터 값이 중간 요소의 값보다 작 으면 전체 검색 범위의 전반부를 새 검색 범위로 사용하고 1) 동일한 값이 발견 될 때까지 실행하십시오.
3) 검색 할 데이터 값이 중간 요소의 값보다 큰 경우 전체 검색 범위의 후반부를 새 검색 범위로 사용하고 동일한 값이 발견 될 때까지 실행하십시오.
4) 결국 동일한 값을 찾을 수없는 경우 오류 메시지가 반환됩니다.
바이너리 트리에 따르면, 중간 값은 이진 트리의 뿌리이고, 상반기는 왼쪽 하위 트리이고, 후반은 오른쪽 하위 트리입니다. 반 찾기 검색 방법에 대한 검색 수는 값이 위치한 계층 수입니다. 동등한 확률로 대략
log2 (n+1) -1
코드 사본은 다음과 같습니다.
// 데이터는 검색 할 배열, X는 검색 할 데이터 값이며 Beg는 검색 범위의 시작이며 마지막은 검색 범위의 끝입니다.
// 비 수수료 방법
int bisearch (int data [], const int x, int beg, int last)
{
int mid; // 중간 위치
if (beg> last)
{
반품 -1;
}
while (beg <= last)
{
mid = (beg + last) / 2;
if (x == data [mid])
{
중간에 반환;
}
else if (data [mid] <x)
{
beg = mid + 1;
}
else if (data [mid]> x)
{
마지막 = 중간 -1;
}
}
반품 -1;
}
// 재귀 방법
int iterbisearch (int data [], const int x, int beg, int last)
{
int mid = -1;
mid = (beg + last) / 2;
if (x == data [mid])
{
중간에 반환;
}
else if (x <data [mid])
{
반환 iterbisearch (data, x, beg, mid -1);
}
else if (x> data [mid])
{
반환 iterbisearch (data, x, mid + 1, last);
}
반품 -1;
}
// 주요 함수
int _tmain (int argc, _tchar* argv [])
{
int data1 [60] = {0};
int no2search = 45;
cout << "배열은 다음과 같습니다."<< endl;
int siz = sizeof (data1)/sizeof (int);
for (int i = 0; i <siz; i ++)
{
데이터 1 [i] = i;
cout << data1 [i] << "";
}
cout << endl;
int index = -1;
// index = bisearch (data1, no2search, 0, siz);
index = iterbisearch (data1, no2search, 0, siz);
cout << ""<< no2search << "의 색인"<< index << endl;
getchar ();
반환 0;
}
코드 사본은 다음과 같습니다.
/**
* 배열에서 문자의 위치를 찾는 절반 (주문 목록)
* @param 배열 검색된 배열
* @param x 캐릭터를 찾을 수 있습니다
* @배열에서 캐릭터의 위치를 returns, 찾을 수 없음 -1
*/
함수 BinarySearch (Array, x) {
var lowpoint = 1;
var higpoint = array.length;
var returnValue = -1;
var midpoint;
var found = false;
while ((lowpoint <= higpoint) && (! found)) {
midpoint = math.ceil ((lowpoint+higpoint)/2);
//console.log(LOGPOING+"===="+MidPoint+"===="+higpoint);
if (x> array [midpoint-1]) {
로우 포인트 = 중간 점+1;
}
else if (x <array [midpoint-1]) {
higpoint = midpoint-1;
}
else if (x = 배열 [midpoint-1]) {
발견 = 참으로;
}
}
if (발견) {
returnValue = midpoint;
}
return returnValue;
}
/*var array2 = [1,2,3,4,5,6,7,8,9,100,109];*/
var array2 = [ 'a', 'b', 'c', 'd', 'e', 'f', 'g'];
Console.log (BinarySearch (Array2, 'C'));