一、LintCode链接
http://www.lintcode.com/zh-cn/problem/first-position-of-target/
二、问题描述
给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。
三、关键点分析
- 升序数组
- 数据量
- n0<=n1<=n2<=....，数据可能连续相等
- 第一次出现的下标
四、解决思路（Java）
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.源码中的二分查找
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
}
