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 比较之前。