给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组中,返回-1。
在线评测地址:
LintCode 领扣
样例 1:
输入:[1,4,4,5,7,7,8,9,9,10],1
输出: 0
样例解释:
第一次出现在第0个位置。
样例 2:
输入: [1, 2, 3, 3, 4, 5, 10],3
输出: 2
样例解释:
第一次出现在第2个位置
样例 3:
输入: [1, 2, 3, 3, 4, 5, 10],6
输出: -1
样例解释:
没有出现过6, 返回-1
解题思路
题目提到,给定的数组已经排序,若从小到大遍历数组查找target,则时间复杂度为O(n)O(n),n为数组长度。需要用一个O(logn)O(logn)的时间复杂度去完成本题,那么需要用到二分查找。
二分查找常用于查找有序数组中目标数target的位置,用left和right记录target所在的区间端点,每次将区间的中间位置值和target作比较,然后移动区间端点。
算法流程
将区间赋值为整个数组区间(left = 0, right = n - 1),取中间位置mid
若a[mid] < target,则将区间缩小到原区间的右区间(left = mid + 1)
若a[mid] >= target,则将区间缩小至原区间的左区间(right = mid)
若left >= right 时,若a[right] = target则返回right, 否则返回-1
复杂度分析
时间复杂度:O(logn)
每次查找都将区间缩小至原来长度的一半,可见查找的最多次数为logn
空间复杂度:O(1)
查找不需要开辟新的非常数级空间,只需在原数组基础上进行查找即可
代码
public 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) {
int left = 0;
int right = nums.length - 1;
int mid;
while (left < right) {
//得到中间位置
mid = (right + left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
if (nums[right] == target) {
return right;
}
return -1;
}
}
更多题解参考: