lintcode 447 Search in a Big Sorted Array（倍增+二分）

题意：给一个按照升序排序的正整数数组。这个数组很大以至于只能通过固定的接口ArrayReader->get(k)来访问第k个数。并且也没有办法得知这个数组有多大。找到给出的整数target第一次出现的位置。你的算法需要在O(logk)的时间复杂度内完成，k为target第一次出现的位置的下标。如果找不到target，返回-1。

思路：倍增找到第一个大于target的位置，然后二分

 class Solve

 {

     int searchBigSortedArray(ArrayReader* reader,int target)

     {

         int index = ;

         while(reader->get(index-)<target)

             index*=;

         int start=,end=index;

         while(start<=end)

         {

             int mid = start+(end-start)/;

             if(reader->get(mid)==target)

                 return mid;

             else if(reader->get(mid)>target)

                 end = mid-;

             else start = mid+;

         }

         return -;

     }

 };

巴特西

lintcode 447 Search in a Big Sorted Array（倍增+二分）

最新文章

热门文章