首页 > 代码库 > Search for a Range leetcode java

Search for a Range leetcode java

2024-07-13 04:15:32   223人阅读

题目：

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].

 

从题目中获取到关键字：sorted array ，find...position, a given target value, O(logn).

这些关键字都在提醒我们这道题的思路应该是二分查找法。


       二分查找方法
       二分查找经常用来在有序的数列查找某个特定的位置。

       因此，应用二分查找法，这个数列必须包含以下特征：

  •  存储在数组中
  • 有序排列

     同时这道题让我们确定 starting position和ending position，这就让我们联想到之前做过的Search Insert Position一题，当无法查找到given target时，利用非递归二分查找法所得的最终low和high指针，将会指向该无法查找到的元素的左右两个元素。说不清楚看例子，例如，给定arraylist [1,2,4,5] target为3，那么通过传统非递归二分查找法，low指针将会指向4（位置为2），high指针指向2（位置为1）。

     利用这种规律，我们就能够找到target元素的左右边界。所以本题的解题思路为：

第一步，在给定数组中找到该target，记录该位置。这时我们并不关心这个target是边界还是中间值，我们只需确定，在数组中是能够找到这样一个target值。如果找不到返回{-1，-1}。为了保证时间复杂度是O(logn), 这里自然而然使用传统二分查找法实现。

第二步，确定该target的右边界。此时我们将对数组从刚才确定的那个target的pos作为起始点，到数组结束，来确定右边界。同样是使用二分查找法，当新的mid值仍然等于target值时，我们能确定该mid左半边（到pos）都是等于target，继续在右半边查找。如果新的mid值不等于target值，我们就知道右边界一定在新mid值的左半边，继续查找。最后新的high指针指向的就是右边界的位置。

第三步，确定该target的左边界。这一步与第二步对称操作，最后新的low指针指向的就是左边界的位置。

最后，返回结果数组。

 

代码如下：

 

 1     public int[] searchRange(int[] A, int target) {
 2         int [] res = {-1,-1};
 3         if(A == null || A.length == 0)
 4             return res;
 5         
 6         //first iteration, find target wherever it is
 7         int low = 0;
 8         int high = A.length-1;
 9         int pos = 0;
10         while(low <= high){
11             int mid = (low + high)/2;
12             pos = mid;
13             if(A[mid] > target)
14                 high = mid - 1;
15             else if(A[mid] < target)
16                 low = mid + 1;
17             else{
18                 res[0] = pos;
19                 res[1] = pos;
20                 break;
21             }
22         }
23         
24         if(A[pos] != target)
25             return res;
26         
27         //second iteration, find the right boundary of this target
28         int newlow = pos;
29         int newhigh = A.length-1;
30         while(newlow <= newhigh){
31             int newmid = (newlow+newhigh)/2;
32             if(A[newmid] == target)
33                 newlow = newmid + 1;
34             else
35                 newhigh = newmid - 1;
36         }
37         res[1] = newhigh;
38         
39         //third iteration, find the left boundary of this target
40         newlow = 0;
41         newhigh = pos;
42         while(newlow <= newhigh){
43             int newmid = (newlow+newhigh)/2;
44             if(A[newmid] == target)
45                 newhigh = newmid - 1;
46             else
47                 newlow = newmid + 1;
48         }
49         res[0] = newlow;
50         
51         return res;
52     }

 Reference:http://blog.csdn.net/linhuanmars/article/details/20593391


联系
我们