LeetCode刷题"/>
【LeetCode刷题
702.搜索长度未知的有序数组
注意:数组是已经排好序的,因此可以将时间复杂度控制在对数级别,意味着需要将问题分解为两个子问题,这两个子问题都应该在对数级别的时间内完成:
- 定义搜索限制,即搜索的左右边界
- 在定义的边界内进行二分查找
定义搜索边界:
选取第一个和第二个索引,即0和1,作为左右边界,如果目标值不在这两个元素之中,那么它就在边界之外,即在右边,意味着左边界可以向右移动,而右边界需要扩展,为了保持对数时间复杂度,让right=right×2来扩展它
如果目标值现在小于右边元素,就完成了,边界已经设置了,如果没有,重复以上两步,直到边界确定为止。
- 将左边界移动到右边:left=right
- 扩大右边界:right=right×2
/*** // This is ArrayReader's API interface.* // You should not implement it, or speculate about its implementation* interface ArrayReader {* public int get(int index) {}* }*/class Solution {public int search(ArrayReader reader, int target) {if(reader.get(0) == target){return 0;}int left=0,right=1;while(reader.get(right) < target){left = right;right = right * 2;}while(left <= right){int mid = left + (right - left) / 2;if(reader.get(mid) == target){return mid;}else if(reader.get(mid) < target){left = mid + 1;}else{right = mid - 1;}}return -1;}
}
更多推荐
【LeetCode刷题
发布评论