[leetcode] #34 Search for a range

Title - #34 Search for a range

Level - Medium

Description - 題目主要是給一個字串 S = [1,2,3]，一個目標數字，列出該數字所在的位置。

(補充)

解法很簡單，雖然要求O(logN)但其實用二分法就可以解決，然後記得一開始找數字時同時更新 left_search跟right_search的boundary。不過我在邊界值處理上花了不少時間... Orz

作法 iteration

1:  //empty list  
2:  if (S.length = 0)  
3:    return new int[]{-1,-1};  
4:  lbp = bp = 0, rep = ep = S.length; // bp = begin point, ep=end point  
5:  min = 0;  
6:  while (1){  
7:    mid = (bp+ep)/2;  
8:    if (bp==mid) break;   
9:    if (S[mid] == target)  
10:     break;  
11:    else if (S[mid] < target)   
12:      lbp = bp = mid;  
13:    else   
14:      rep = ep = mid;   
15:  }  
16:  // target number is not existed.  
17:  if (S[mid] != target)  
18:    return new int[]{-1,-1};  
19:  // update search boundary  
20:  rbp = lep = mid;  
21:  // left search  
22:  while (1){  
23:    tmid = (lbp+lep)/2;  
24:    if (lbp==tmid) break;   
25:    if (S[tmid] < target)   
26:      lbp = tmid;  
27:    else   
28:      lep = tmid;   
29:  }  
30:  if (S[lbp]==target)  
31:   lep = lbp;  
32:  //right search  
33:  while (1){  
34:    tmid = (rbp+rep)/2;  
35:    if (bp==tmid) break;   
36:    if (S[tmid] < target)   
37:      rbp = tmid;  
38:    else   
39:      rep = tmid;   
40:  }  
41:  return new int[]{lep, rbp};