배열 - 2 분 찾기
http://www.lintcode.com/zh-cn/problem/first-position-of-target/
2. 문제 설명
정렬 된 정수 배열 (오름차 순) 과 찾 을 정수 target 을 지정 합 니 다. O (logn) 의 시간 으로 target 이 처음 나타 난 아래 표 시 를 찾 습 니 다 (0 부터). target 이 배열 에 존재 하지 않 으 면 - 1 로 돌아 갑 니 다.
3. 관건 적 인 분석
1. 데이터 양 이 많 지 않 고 재 귀 법 과 비 재 귀 법
귀속 법
public int binarySearch(int[] nums, int fromIndex, int toIndex, int target) {
if (nums == null || nums.length <= 0
|| fromIndex > toIndex || fromIndex < 0 || toIndex >= nums.length) {
return -1;
}
int midIndex = (fromIndex + toIndex) >>> 1;
int midValue = nums[midIndex];
if (midValue < target) {
return binarySearch(nums, midIndex + 1, toIndex, target);
} else if (midValue > target) {
return binarySearch(nums, fromIndex, midIndex - 1, target);
} else {
int beforeIndex = binarySearch(nums, fromIndex, midIndex - 1, target);
return beforeIndex > 0 ? beforeIndex : midIndex;
}
}
비 귀속 법
public int binarySearch(int[] nums, int target) {
if (nums == null || nums.length <= 0) {
return -1;
}
int resultIndex = -1;
int fromIndex = 0;
int toIndex = nums.length - 1;
while (fromIndex <= toIndex) {
int midIndex = (fromIndex + toIndex) >>> 1;
int midValue = nums[midIndex];
if (midValue < target) {
fromIndex = midIndex + 1;
} else if (midValue > target) {
toIndex = midIndex - 1;
} else {
resultIndex = midIndex;
toIndex = midIndex - 1;
}
}
return resultIndex;
}
2. 데이터 양 이 많 으 면 트 리 나 더미 와 Quick Select 알고리즘 (TODO) 을 사용 합 니 다.
관련
1. 소스 코드 의 2 분 찾기
SparseArray.get :
public E get(int key, E valueIfKeyNotFound) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i < 0 || mValues[i] == DELETED) {
return valueIfKeyNotFound;
} else {
return (E) mValues[i];
}
}
ContainerHelpers.binarySearch() :
static int binarySearch(int[] array, int size, int value) {
int lo = 0;
int hi = size - 1;
while (lo <= hi) {
final int mid = (lo + hi) >>> 1;
final int midVal = array[mid];
if (midVal < value) {
lo = mid + 1;
} else if (midVal > value) {
hi = mid - 1;
} else {
return mid; // value found // ,
}
}
return ~lo; // value not present
}
2. 링크
위 키. - 2 분 검색.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.