前言
最近快回家了，虽然用印象笔记管理自己每天的计划，仍然免不了每天有贪玩或者完不成当天任务的情况，当做年前放松了，年后去了云os实习，而且都是自己没接触过的新内容，压力还挺大
这篇博客主要是复习一下二分查找算法，记得有人曾经说过90%的程序员写不对二分查找，哈哈，我们争取做那10%
题目
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm‘s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
Your algorithm‘s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
思路1&&AC代码1
首先是二分查找，然后根据二分查找的坐标分别向前、向后查找即可
平均时间复杂度是O（logn），但是最坏情况下可能达到O（n）（ps：当输入数据均相等，且target也跟输入数据相同时）
AC代码
public class Solution {
public static int[] searchRange(int[] A, int target) {
int res[] = new int[2], bt = 0, ed = A.length - 1, mid = 0;
while (bt <= ed) {
mid = bt + ((ed - bt) >> 1);
if (A[mid] == target) {
break;
} else if (A[mid] > target) {
ed = mid - 1;
} else {
bt = mid + 1;
}
}
if (bt > ed) { // not found
res[0] = res[1] = -1;
} else { // found
int is, ie;
is = mid;
while (is - 1 >= 0 && A[is - 1] == target) {
is -= 1;
}
ie = mid;
while (ie + 1 < A.length && A[ie + 1] == target) {
ie += 1;
}
res[0] = is;
res[1] = ie;
}
return res;
}
}
思路2&&AC代码
两次二分查找，第一次确定开始点，第二次确定结束点，这样省去了思路1最后时间复杂度为O(n)的朝两个方向查找的过程
AC代码
public class Solution {
public static int[] searchRange(int[] A, int target) {
int res[] = new int[2], bt, ed, mid;
res[0] = res[1] = -1;
bt = mid = 0;
ed = A.length - 1;
while (bt < ed) {
mid = bt + ((ed - bt) >> 1);
if (A[mid] < target) {
bt = mid + 1;
} else {
ed = mid;
}
}
if (A[bt] != target) {
return res;
} else {
res[0] = bt;
}
bt = mid = 0;
ed = A.length;
while (bt < ed) {
mid = bt + ((ed - bt) >> 1);
if (A[mid] > target) {
ed = mid;
} else {
bt = mid + 1;
}
}
res[1] = ed - 1;
return res;
}
}