搜索

给出一个有序数组,请在数组中找出目标值的起始位置和结束位置


发布时间: 2022-11-24 18:42:01    浏览次数:67 次

给出一个有序数组,请在数组中找出目标值的起始位置和结束位置
你的算法的时间复杂度应该在O(log n)之内
如果数组中不存在目标,返回[-1, -1].

例如:
给出的数组是[50, 70, 70, 80, 80, 100],目标值是80,
返回[3, 4].


/**
** 两次二分查找
**/
public int[] searchRange (int[] A, int target) { int left = findIndex(A, target, true); int right = findIndex(A, target, false); return new int[]{left,right}; } int findIndex(int[] A, int target, boolean leftFlag){ int start = 0; int end = A.length-1; int index = -1; while(start<=end){ int mid =(start+end)/2; if(A[mid]>target){ end = mid-1; }else if(A[mid]<target){ start = mid +1; }else{ index = mid; if(leftFlag){ end = mid -1; }else{ start = mid+1; } } } return index; }

 

免责声明 给出一个有序数组,请在数组中找出目标值的起始位置和结束位置,资源类别:文本, 浏览次数:67 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-24 06:42:01。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://www.cnblogs.com/shijianchuzhenzhi/p/16001374.html