博客

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
  

/*
*  interface Dictionary {
*    public Integer get(int index);
*  }
*/

// You do not need to implement the Dictionary interface.
// You can use it directly, the implementation is provided when testing your solution.
public class Solution {
  public int search(Dictionary dict, int target) {
    // Write your solution here
    //corner case 
    if(dict == null){
        return -1 ; 
    }
       //corner case: index 0 == target
    if(dict.get(0) != null && dict.get(0) == target){
        return 0 ; 
    }
    int left = 1 ; 
    while(dict.get(left) != null && dict.get(left)<target){
        left *= 2 ; 
    }
    int start = left/2 , end = left ; 
    while(start +1 < end){
        int mid = start + (end - start)/2 ; 
         if(dict.get(mid) != null && dict.get(mid) == target){
          return mid ; 
      } else if(dict.get(mid)!= null && dict.get(mid) < target){
          start = mid ; 
      } else{
          end = mid ; 
      }
    }
    //post processing
    if(dict.get(start)!= null && dict.get(start) == target){
        return start ; 
    } 
    if(dict.get(end)!= null && dict.get(end) == target){
        return end ; 
    }
    return -1;
  }
}

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