LeetCode--034--在排序数组中查找元素的第一个和最后一个位置（java）

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

 1 class Solution {
 2     public int[] searchRange(int[] nums, int target) {
 3         if(nums == null || nums.length == 0)return new int[]{-1,-1};
 4         return new int[]{findFirst(nums,target),findLast(nums,target)};
 5     }
 6     public int findFirst(int[] nums,int target){
 7         int start = 0;
 8         int end = nums.length - 1;
 9         while(start + 1 < end){
10             int mid = (end - start) / 2 + start;
11             if(nums[mid] < target){
12                 start = mid;
13             }else{
14                 end = mid;
15             }
16         }
17         if(nums[start] == target) return start;
18         if(nums[end] == target) return end;
19         return -1;
20     }
21     public int findLast(int[] nums,int target){
22         int start = 0;
23         int end = nums.length - 1;
24         while(start + 1 < end){
25             int mid = (end - start) / 2 + start;
26             if(nums[mid] > target){
27                 end = mid;
28             }else{
29                 start = mid;
30             }
31         }
32         if(nums[end] == target) return end;
33         if(nums[start] == target) return start;  
34         return -1;
35     }
36     
37 }

方法2：(unpassed) 长度小于3会有错误

 1 class Solution {
 2     public int[] searchRange(int[] nums, int target) {
 3         if(nums == null || nums.length == 0)return new int[]{-1,-1};
 4         if(nums.length == 1 && nums[0] == target) return new int[]{0,0};
 5         int start = 0,end = nums.length -1;
 6         boolean flag = false;
 7         while(start+1<end ){
 8             int mid = (end - start) / 2  + start;
 9             if(nums[mid] < target){
10                 start = mid;
11             }else if(nums[mid] > target){
12                 end = mid;
13             }else{
14                 flag = true;
15                 start = mid;
16                 end = mid;
17                 while(start >= 0 && nums[start] == target){
18                     start--;
19                 }
20                 while(end < nums.length && nums[end] == target){
21                     end++;
22                 }
23                 start++;
24                 end--;
25                 break;
26             }
27         }
28         if(flag == true){
29             return new int[]{start,end};
30         }
31         return new int[]{-1,-1};
32     }
33     
34     
35 }

2019-04-27 19:51:51