몇 가지 2 분. - 자바.
/**
* 各种 二分
* 相同key最小下标,最大下标
* 小于key的最大下标
* 大于key的最小下标
* 数组升序排序, 找不到都返回-1
*
* @author: Guanpx [email protected]
* @create: 2018-11-26 09:35:50
**/
public class BinSearch {
//查找相同key的最小下标
//思路:向左一直找,最后的位置就是结果或者找不到
public static int low_search(int[] arr, int key) {
int l = 0;
int r = arr.length - 1; //下标减一
while (l <= r) {
int mid = (l + r) >> 1;
if (arr[mid] >= key) { //注意这种情况
r = mid - 1;
} else {
l = mid + 1;
}
}
if (l < arr.length && arr[l] == key) {
return l;
}
return -1;
}
//查找相同key的最大下标
public static int high_search(int[] arr, int key) {
int l = 0;
int r = arr.length - 1; //下标减一
while (l <= r) {
int mid = (l + r) >> 1;
if (arr[mid] > key) {
r = mid - 1;
} else if (arr[mid] <= key) { //注意这种情况
l = mid + 1;
}
}
if (r >= 0 && arr[r] == key) {
return r;
}
return -1;
}
// 小于当前k的最大下标值
public static int small_search(int[] arr, int key) {
int l = 0;
int r = arr.length - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (arr[mid] >= key) {
r = mid - 1;
} else
l = mid + 1;
}
return r; //r会越界,变为-1,此情况直接返回
}
// 大于当前key的最小下标值
public static int big_search(int[] arr, int key) {
int l = 0;
int r = arr.length - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (arr[mid] > key) {
r = mid - 1;
} else if (arr[mid] <= key)
l = mid + 1;
}
return l >= arr.length ? -1 : l; // 如果越界,即找不到大于key的,则返回-1
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Java 이분 검색 알고리즘 실례 분석 실현본고는 자바 구현 이분 검색 알고리즘을 실례로 다루고 있다.여러분에게 참고할 수 있도록 나누어 드리겠습니다.구체적으로 다음과 같습니다. 1. 전제: 2분 찾기의 전제는 찾아야 할 수조가 이미 정렬되어 있어야 한다는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.