LeetCodeOnlineJudge题目C#练习-SearchforaRange

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Node.js›Node.js教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

 1         public static List<int> SearchforaRange(int[] A, int target)
 2         {
 3             List<int> ret = new List<int>();
 4 
 5             ret.Add(BinarySearchlow(A, 0, A.Length - 1, target));
 6             ret.Add(BinarySearchup(A, 0, A.Length - 1, target));
 7 
 8             return ret;
 9         }
10 
11         public static int BinarySearchlow(int[] A, int start, int end, int target)
12         {
13             if (start > end)
14                 return -1;
15 
16             int mid = start + ((end - start) / 2);
17             if(A[mid] == target && (mid == 0 || A[mid - 1] < target))
18             {
19                 return mid;
20             }
21             else if (A[mid] < target)
22             {
23                 return BinarySearchlow(A, mid + 1, end, target);
24             }
25             else
26             {
27                 return BinarySearchlow(A, start, mid - 1, target);
28             }
29         }
30 
31         public static int BinarySearchup(int[] A, int start, int end, int target)
32         {
33             if (start > end)
34                 return -1;
35 
36             int mid = start + ((end - start) / 2);
37             if (A[mid] == target && (mid == end || A[mid + 1] > target))
38             {
39                 return mid;
40             }
41             else if (A[mid] > target)
42             {
43                 return BinarySearchup(A, start, mid - 1, target);
44             }
45             else
46             {
47                 return BinarySearchup(A, mid + 1, end, target);
48             }
49         }