Search in Unknown Sized Sorted Array

  • Post author:
  • Post category:其他



Given a integer dictionary A of unknown size, where the numbers in the dictionary are sorted in ascending order, determine if a given target integer T is in the dictionary. Return the index of T in A, return -1 if T is not in A.


Assumptions


  • dictionary A is not null

  • dictionary.get(i) will return null(Java)/INT_MIN(C++) if index i is out of bounds


Examples


  • A = {1, 2, 5, 9, ……}, T = 5, return 2

  • A = {1, 2, 5, 9, 12, ……}, T = 7, return -1
 1 /*
 2 *  interface Dictionary {
 3 *    public Integer get(int index);
 4 *  }
 5 */
 6 
 7 // You do not need to implement the Dictionary interface.
 8 // You can use it directly, the implementation is provided when testing your solution.
 9 public class Solution {
10   public int search(Dictionary dict, int target) {
11     // Write your solution here
12     //corner case 
13     if(dict == null){
14         return -1 ; 
15     }
16        //corner case: index 0 == target
17     if(dict.get(0) != null && dict.get(0) == target){
18         return 0 ; 
19     }
20     int left = 1 ; 
21     while(dict.get(left) != null && dict.get(left)<target){
22         left *= 2 ; 
23     }
24     int start = left/2 , end = left ; 
25     while(start +1 < end){
26         int mid = start + (end - start)/2 ; 
27          if(dict.get(mid) != null && dict.get(mid) == target){
28           return mid ; 
29       } else if(dict.get(mid)!= null && dict.get(mid) < target){
30           start = mid ; 
31       } else{
32           end = mid ; 
33       }
34     }
35     //post processing
36     if(dict.get(start)!= null && dict.get(start) == target){
37         return start ; 
38     } 
39     if(dict.get(end)!= null && dict.get(end) == target){
40         return end ; 
41     }
42     return -1;
43   }
44 }

注意判断 dict.get(i) != null 在和 target 比较之前。

转载于:https://www.cnblogs.com/davidnyc/p/8572352.html