首页 > 其他 > 详细

[LintCode] 447 Search in a Big Sorted Array

时间:2017-04-24 09:35:34      阅读:207      评论:0      收藏:0      [点我收藏+]

Description
Given a big sorted array with positive integers sorted by ascending order. The array is so big so that you can not get the length of the whole array directly, and you can only access the kth number by ArrayReader.get(k) (or ArrayReader->get(k) for C++). Find the first index of a target number. Your algorithm should be in O(log k), where k is the first index of the target number.

Return -1, if the number doesn‘t exist in the array.

Notice
If you accessed an inaccessible index (outside of the array), ArrayReader.get will return 2,147,483,647.

4/23/2017

算法班

注意题目要求是返回第一个index

 1     public int searchBigSortedArray(ArrayReader reader, int target) {
 2         // ArrayReader.get(k);
 3         int startIndex = 0;
 4         while (reader.get(startIndex) < target) {
 5             startIndex *= 2;
 6         }
 7         int start = startIndex / 2, end = startIndex;
 8 
 9         while (start + 1 < end) {
10             int mid = start + (end - start) / 2;
11             if (reader.get(mid) >= target) {
12                 end = mid;
13             } else {
14                 start = mid;
15             }
16         }
17         if (reader.get(start) == target) return start;
18         if (reader.get(end) == target) return end;
19         return -1;
20     }

 

[LintCode] 447 Search in a Big Sorted Array

原文:http://www.cnblogs.com/panini/p/6755128.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!