题目
有序非递减数组，找出在指定区间中的元素位置，输出起始和结束位置的下标。
如数组： 1,2,2,3,4,6
区间:2,8(大于等于2，小于等于8)
结果1,5（1是符合区间最左边的下标，5是符合区间最右边的下标）
要求时间复杂度要小于O(N)(不可以是O(N))
解法1:二分查找
private int[] array = {1,2,2,3,4,6};
private int min = -20;
private int max = 8;
public void binarySearch() {
int left = binarySearch(array,min,true);
int right = binarySearch(array,max,false);
System.out.println(left +" "+ right);
}
private int binarySearch(int[] array,int target,boolean first){
int length = array.length;
if (length == 0) {
return -1;
}
if (array[0] > max) {
return -1;
}
if (array[length-1] < min) {
return -1;
}
int left = 0,right = length -1;
while (left <= right) {
int mid = left + (right -left)/2;
if (array[mid] > target) {
right = mid - 1;
}else if (array[mid] < target) {
left = mid + 1;
}else {
if (first) {
if (mid == 0 || array[mid - 1] != target) {
return mid;
} else {
right = mid - 1;
}
} else {
if (mid == 0 || array[mid + 1] != target) {
return mid;
} else {
left = mid + 1;
}
}
}
}
if (first) {
return left;
} else {
return right;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由半码博客整理，本文链接：https://www.bmabk.com/index.php/post/15009.html
