C 언어 데이터 구조 에서 2 분 검색 재 귀 비 재 귀 실현 및 분석
선언:
2 분 검색 은 질서 있 는 수열 을 찾 는 과정 에서 알고리즘 의 복잡 도가 낮 고 효율 이 높다.그래서 우리 에 게 인기 가 많다.사실 이분 검색 알고리즘 은 매우 고전적 인 알고리즘 이다.하지만 틀 리 기 쉽다.항상 불완전한 국경 문 제 를 고려 하기 때문이다.
재 귀적 이지 않 고 간단하게 분석 해 보 세 요.작성 과정 에서 다음 코드 를 작성 했다 면:
#include<iostream>
#include<assert.h>
using namespace std;
int binaty_search(int* arr, size_t n, int x)
{
assert(arr);
int left = 0;
int right = n - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (x < arr[mid])
{
right = mid-1;
}
else if (x > arr[mid])
{
left = mid+1;
}
else
return mid;
}
return -1;
}
int main()
{
int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 0) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 1) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 2) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 3) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 4) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 5) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 6) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 7) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 8) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 9) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 10) << endl;
return 0;
}
그러면 우 리 는 간단하게 분석 할 수 있다.다음 과 같은 코드 가 구현 된다 면:
#include<iostream>
#include<assert.h>
using namespace std;
int binaty_search(int* arr, size_t n, int x)
{
assert(arr);
int left = 0;
int right = n;
while (left < right)
{
int mid = (left + right) / 2;
if (x < arr[mid])
{
right = mid;
}
else if (x > arr[mid])
{
left = mid + 1;
}
else
return mid;
}
return -1;
}
int main()
{
int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 0) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 1) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 2) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 3) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 4) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 5) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 6) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 7) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 8) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 9) << endl;
cout << binaty_search(arr, sizeof(arr) / sizeof(int), 10) << endl;
return 0;
}
그러면 간단하게 분석 해 볼 수 있다.마찬가지 로 재 귀 실현 조건 도 두 가지 로 나 뉘 는데 저 는 한 가지 만 보 여 드 리 겠 습 니 다.코드 는 다음 과 같 습 니 다.
#include<iostream>
#include<assert.h>
using namespace std;
int binaty_srarch(int* arr, int x, int left, int right)
{
assert(arr);
int mid;
if (left <= right)
{
mid = (left + right) / 2;
if (arr[mid] == x)
{
return mid;
}
else
if (x < arr[mid])
{
return binaty_srarch(arr, x, left, right - 1);
}
else if (x>arr[mid])
{
return binaty_srarch(arr, x, left + 1, right);
}
}
return -1;
}
int main()
{
int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
cout << binaty_srarch(arr, 0, 0, (sizeof(arr) / sizeof(int)) - 1) << endl;
cout << binaty_srarch(arr, 1, 0, (sizeof(arr) / sizeof(int)) - 1) << endl;
cout << binaty_srarch(arr, 2, 0, (sizeof(arr) / sizeof(int)) - 1) << endl;
cout << binaty_srarch(arr, 3, 0, (sizeof(arr) / sizeof(int)) - 1) << endl;
cout << binaty_srarch(arr, 4, 0, (sizeof(arr) / sizeof(int)) - 1) << endl;
cout << binaty_srarch(arr, 5, 0, (sizeof(arr) / sizeof(int)) - 1) << endl;
cout << binaty_srarch(arr, 6, 0, (sizeof(arr) / sizeof(int)) - 1) << endl;
cout << binaty_srarch(arr, 7, 0, (sizeof(arr) / sizeof(int)) - 1) << endl;
cout << binaty_srarch(arr, 8, 0, (sizeof(arr) / sizeof(int)) - 1) << endl;
cout << binaty_srarch(arr, 9, 0, (sizeof(arr) / sizeof(int)) - 1) << endl;
cout << binaty_srarch(arr, 10, 0, (sizeof(arr) / sizeof(int)) - 1) << endl;
return 0;
}
읽 어 주 셔 서 감사합니다. 여러분 에 게 도움 이 되 기 를 바 랍 니 다.본 사이트 에 대한 여러분 의 지지 에 감 사 드 립 니 다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
C 언어 체인 시계는 뱀을 탐식하는 작은 게임을 실현한다본고의 실례는 여러분에게 C 언어 체인표가 뱀 탐식 게임을 실현하는 구체적인 코드를 공유하여 참고하도록 하였으며, 구체적인 내용은 다음과 같다. 프로젝트 이름: 뱀놀이 운영 환경: Linux 프로그래밍 언어: C 언...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.