[데이터 구조] 반절 찾기

절반 으로 나누다
1) 기본 사상
먼저, 표 의 요 소 는 오름차 순 으로 배열 되 고 표 중간 위치 에 기 록 된 키 워드 를 검색 키워드 와 비교 하 며 이들 이 같 으 면 성공 적 으로 찾 을 수 있다 고 가정 합 니 다.그렇지 않 으 면 중간 위치 기록 을 이용 하여 시 계 를 앞, 뒤 두 개의 서브 시트 로 나 누고 중간 위치 기록 의 키워드 가 키 워드 를 찾 는 것 보다 크 면 앞의 서브 시트 를 찾 고 그렇지 않 으 면 뒤의 서브 시트 를 찾 습 니 다.이상 의 과정 을 반복 합 니 다. 조건 에 맞 는 기록 을 찾 아 검색 에 성공 하거나 하위 표 가 존재 하지 않 을 때 까지 찾 을 수 없습니다 O（log N） 。
2) 분석
4. 567914. 비교 횟수 가 적 고 검색 속도 가 빠 르 며 평균 성능 이 좋 으 며 시스템 메모리 사용량 이 비교적 적다 대기 표 가 질서 표 이 고 삭제 가 어렵 습 니 다.따라서 반절 찾기 방법 은 자주 변동 하지 않 고 빈번 한 서열 표를 찾 는 데 적용 된다.
3) 코드 는 다음 과 같다.

int  main()
{
	int arr[] = { 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	int key = 1;
	int left = 0;
	int right = sizeof(arr) / sizeof(arr[0]) - 1;
	while (left <= right)
	{
		int mid = left + (right - left) / 2;
		if (arr[mid] == key)
		{
			printf("      %d
", mid);
			break;
		}
		else if (arr[mid] > key)
		{
			right = mid - 1;
		}
		else if (arr[mid] < key)
		{
			left = mid + 1;
		}
	}
	if (left >= right)

		printf("   
");
	system("pause");
	return 0;
}

2 분 검색 함수 구현:

int binary_search(int *arr, int  key,int left,int right)
{
	while (left <= right)
	{
		int mid = left + (right - left) / 2;
		if (key == arr[mid])
		{
			return mid;
		}
		else if (key < arr[mid])
		{
			right = mid - 1;
		}
		else  if (key>arr[mid])
		{
			left = mid + 1;
		}
	}
			return -1;
}