LintCode 14. First Position of Target 原创Java参考解答
问题描述
http://www.lintcode.com/en/problem/first-position-of-target/
For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity.
If the target number does not exist in the array, return -1.
Example
If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.
解题思路
- 先检查数组nums是否为null或者为空数组，若是则直接返回-1。
- 用二分法在数组中查找target值的位置。若查到了，不直接返回该target位置，而是继续以该位置开始的前面部分继续进行二分查找。以此来查找target在数组中第一次出现的位置。
参考代码
class Solution {
/**
* @param nums: The integer array.
* @param target: Target to find.
* @return: The first position of target. Position starts from 0.
*/
public int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0;
int end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
end = mid;
} else if (nums[mid] > target) {
end = mid;
} else {
start = mid;
}
}
if (nums[start] == target) {
return start;
} else if (nums[end] == target) {
return end;
}
return -1;
}
}