몇 가지 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 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
귀속할 필요가 없는 2점 찾기오늘 동료가 차에서 나에게 면접을 본다고 했는데, 이 문제가 있었는데, 그는 해내지 못했다 회사에 가서 직접 간단히 썼다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.