java 이분법 몇 가지 실현 방법 상세히 설명
2분 찾기 (java 구현)
이분 찾기
알고리즘 사상: 반절찾기라고도 하는데 찾을 서열이 질서정연해야 한다.매번 중간 위치의 값을 추출하여 대기 키워드와 비교한다. 만약에 중간 위치의 값이 대기 키워드보다 크면 앞부분에서 이 검색 과정을 순환하고, 중간 위치의 값이 대기 키워드보다 작으면 뒷부분에서 이 검색 과정을 순환한다.찾을 때까지 검색하지 않으면 시퀀스에 검색할 키워드가 없습니다.
구현:
1.비귀속 코드
public static int biSearch(int []array,int a){
int lo=0;
int hi=array.length-1;
int mid;
while(lo<=hi){
mid=(lo+hi)/2;
if(array[mid]==a){
return mid+1;
}else if(array[mid]<a){
lo=mid+1;
}else{
hi=mid-1;
}
}
return -1;
}
public static int sort(int []array,int a,int lo,int hi){
if(lo<=hi){
int mid=(lo+hi)/2;
if(a==array[mid]){
return mid+1;
}
else if(a>array[mid]){
return sort(array,a,mid+1,hi);
}else{
return sort(array,a,lo,mid-1);
}
}
return -1;
}
첫 번째 요소가 나타나는 위치를 찾습니다 (요소는 반복 가능)
public static int biSearch(int []array,int a){
int n=array.length;
int low=0;
int hi=n-1;
int mid=0;
while(low<hi){
mid=(low+hi)/2;
if(array[mid]<a){
low=mid+1;
}else{
hi=mid;
}
}
if(array[low]!=a){
return -1;
}else{
return low;
}
}
public static int biSearch(int []array,int a){
int n=array.length;
int low=0;
int hi=n-1;
int mid=0;
while(low<hi){
mid=(low+hi+1)/2;
if(array[mid]<=a){
low=mid;
}else{
hi=mid-1;
}
}
if(array[low]!=a){
return -1;
}else{
return hi;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
38. Java의 Leetcode 솔루션텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
