力扣 查找元素的位置

二分查找经典例题。
标题

要是只是从数组中用二分查找对应的元素，套一下模板一下就可以得出了，然后这题就在于此中会有多个目标元素，要用差别的方式在找到第一个元素时再做偏移。
时间复杂度：O(log n)，空间复杂度：O(1)。

1. class Solution {
2.     public int[] searchRange(int[] nums, int target) {
3.         int left = 0;
4.     int right = nums.length - 1;
5.     int first = -1;
6.     int last = -1;
7.     // 找第一个等于target的位置
8.     while (left <= right) {
9.       int middle = (left + right) / 2;
10.       if (nums[middle] == target) {
11.         first = middle;
12.         right = middle - 1; //找到后继续往左，直到找到第一个等于target的位置
13.       } else if (nums[middle] > target) {
14.         right = middle - 1;
15.       } else {
16.         left = middle + 1;
17.       }
18.     }
20.     // 最后一个等于target的位置
21.     left = 0;
22.     right = nums.length - 1;
23.     while (left <= right) {
24.       int middle = (left + right) / 2;
25.       if (nums[middle] == target) {
26.         last = middle;
27.         left = middle + 1; //找到后继续往右，直到找到最后一个等于target的位置
28.       } else if (nums[middle] > target) {
29.         right = middle - 1;
30.       } else {
31.         left = middle + 1;
32.       }
33.     }
35.     return new int[]{first, last};
36.     }
37. }

复制代码

接着也可以套常见的两种二分模板。
一种是将区间[l,r]划分成[l,mid]和[mid+1,r]时，其更新操纵是r=mid大概l=mid+1，盘算mid时不需要加1，即mid=(l+r)/2。 

1. while (l < r)
2.     {
3.         int mid = (l + r)/2;
4.         if (check(mid)) r = mid;
5.         else l = mid + 1;
6.     }

复制代码

一种是将区间[l,r]划分成[l,mid−1]和[mid,r]时，其更新操纵是r=mid−1大概l=mid，此时为了防止不断循环，盘算mid时需要加1，即mid=(l+r+1)/2。

1. while (l < r)
2.     {
3.         int mid = ( l + r + 1 ) /2;
4.         if (check(mid)) l = mid;
5.         else r = mid - 1;
6.     }

复制代码

然后用两种差别的二分查找方式即可以找到数组中目标元素的第一个和末了一个位置了。
时间复杂度：O(log n)，空间复杂度：O(1)。

1. class Solution {
2.     public int[] searchRange(int[] nums, int target) {
3.         if(nums.length == 0) return new int[]{-1,-1};
4.    
5.         int low = 0, r = nums.length - 1;
6.         while( l < r)                               
7.         {
8.             int mid = (l + r )/2;
9.             if(nums[mid] >= target) r = mid;
10.             else l = mid + 1;
11.         }
12.         if( nums[r] != target) return new int[]{-1,-1};
13.         int L = r;
14.         l = 0; r = nums.length - 1;   
15.         while( l < r)                                
16.         {
17.             int mid = (l + r +1)/2;
18.             if(nums[mid] <= target ) l = mid;
19.             else r = mid - 1;
20.         }
21.         return new int[]{L,r};
22.     }
23. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。