자바 데이터 구 조 는 반절 검색 알고리즘 프로 세 스 분석 을 실현 합 니 다.

반절 찾기 기술,즉 이분 찾기 를 통상 이분법 찾기 라 고 부른다.그의 전 기 는 선형 표 중의 기록 이 반드시 관건 적 인 코드 가 질서 가 있어 야 한다(보통 큰 것 에서 작은 질서 까지).선형 표 는 반드시 순서 적 으로 저장 하고 반 으로 찾 아야 하 는 기본 사상 은 다음 과 같다.
중간 기록 을 비교 대상 으로 하고 주어진 값 이 중간 기록 의 키워드 와 같 으 면 중간 에 기 록 된 키워드 가 같 으 면 찾 는 데 성공 합 니 다.주어진 값 이 중간 기록 의 절반 보다 작 으 면 계속 찾 아 보 세 요.중간 기록 보다 주어진 값 이 큰 키 워드 는 중간 기록 의 오른쪽 부분 에서 계속 찾 습 니 다.검색 에 성공 하거나 모든 검색 영역 이 기록 되 지 않 고 검색 에 실패 할 때 까지 상기 과정 을 계속 반복 합 니 다.
텍스트 배열 에 서 는 절반 으로 찾 아야 합 니 다.배열 에 숫자 가 있 는 지 찾 아야 합 니 다.
알고리즘 은 위 경계 hi,아래 경계 lo 를 유지 하고 있 습 니 다.예 를 들 어 88 이라는 숫자 를 찾 아야 합 니 다.
데이터 상태 초기 화
​
아래 그림 은 88 이분법 의 절 차 를 조회 하 라 는 뜻 이다.
​
​
​
​
​
​
구현 방식:
먼저 우 리 는 찾 으 려 는 데이터 에 대해 순 서 를 정 한 다음 에 재 귀적 호출 방식 으로 반 으로 찾 습 니 다.순 서 를 정 한 배열 과 찾 을 값 을 지정 하 는 동시에 왼쪽 경계 와 오른쪽 경 계 를 지정 합 니 다.

/**
*            
*
* @param array       
* @param value     
* @param left    ，              
* @param right    ，              
* @return            ，        -1
*
*/
static int binarySearch(int[] array,int value, int left,int right){
if(left>right){ //    
 return -1; //        
}
int mid =(left + right) >>>1 ;//   mid=(left + right)/2
if(array[mid] == value){
 return mid;
}else if (array[mid] > value){
 //        
 return binarySearch(array,value,left,mid-1); 

}else {
 //        
 return binarySearch(array,value,mid+1,right);
}
}

재 귀적 이지 않 은 방법 으로 반절 탐색 을 실현 하 다.

static int binarySearch(int[] array,int value, int left,int right){
 int low = left;//    
 int high = right -1; //    
 while(low <= high){
  int mid =(low + high)>>>1; //   mid = (low + right)/2
  int midVal = array[mid]; //    
  if(midVal < value){ //              
   low = mid +1;
  }else if(midVal > value){ //              
   high = mid -1;
  }else {
   return mid; //    ，       
  }
 }
 return -(low+1); //   ，    
}

주의해 야 할 것 은 반절 조 회 는 정렬 된 배열 에 의존한다.정렬 되 지 않 은 배열 이 라면 절반 으로 찾 을 수 없습니다.우선 정렬 처리 가 필요 합 니 다.
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.