【LeetCode刷题

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;}
}