34.Find First and Last Position of Element in Sorted Array---头条面试题、《剑指offer》38

题目大意：找出一串升序数组中target值的起始下标和结束下标值，如果不存在则返回{-1，-1}。

解法一：用二分查找，找到数组中的target，然后找其左边和右边的target下标值。代码如下（耗时11ms）：

 1     public int[] searchRange(int[] nums, int target) {
 2         if(nums == null || nums.length == 0) {
 3             int[] r = {-1, -1};
 4             return r;
 5         }
 6         int low = 0, high = nums.length - 1;
 7         int start = -1, end = -1;
 8         while(low <= high) {
 9             int mid = (low + high) / 2;
10             if(nums[mid] < target) {
11                 low = mid + 1;
12             }
13             else if(nums[mid] > target) {
14                 high = mid - 1;
15             }
16             else {
17                 //找左边起始下标
18                 for(int i = mid; i >= 0; i--) {
19                     if(nums[i] == target) {
20                         start = i;
21                     }
22                     else {
23                         break;
24                     }
25                 }
26                 //找右边终止下标
27                 for(int i = mid; i < nums.length; i++) {
28                     if(nums[i] == target) {
29                         end = i;
30                     }
31                     else {
32                         break;
33                     }
34                 }
35                 break;
36             }
37         }
38         int[] res = {start, end};
39         return res;
40     }

View Code

解法二：直接暴力，一次遍历，找重复值。代码如下（耗时10ms）：

 1     public int[] searchRange(int[] nums, int target) {
 2         int start = -1, end = -1;
 3         boolean mark = false;
 4         for(int i = 0; i < nums.length; i++) {
 5             if(nums[i] == target) {
 6                 if(mark == false) {
 7                     start = end = i;
 8                     mark = true;
 9                 }
10                 else {
11                     end = i;
12                 }
13             }
14         }
15         int[] res = {start, end};
16         return res;
17     }

View Code

解法三：真正的二分查找。法一其实复杂度还是o(n)。应该先对起始下标进行二分查找，然后再对结束下标进行二分查找。代码如下（耗时5ms）：

 1     public int[] searchRange(int[] nums, int target) {
 2         int left = 0, right = nums.length - 1;
 3         int[] res = {-1, -1};
 4         if(nums.length == 0) {
 5             return res;
 6         }
 7         //二分找到起始下标
 8         while(left < right) {
 9             int mid = (left + right) / 2;
10             //这里比较左值，如果<，则left更新，否则left不会更新
11             //所以left不更新有两种情况：>或=
12             if(nums[mid] < target) {
13                 left = mid + 1;
14             }
15             //这里统统修改右值
16             else {
17                 right = mid;
18             }
19         }
20         if(nums[left] != target) {
21             return res;
22         }
23         res[0] = left;
24         left = 0;
25         right = nums.length - 1;
26         //二分找到结束下标
27         while(left < right) {
28             //这里要+1，否则会出错
29             int mid = (left + right) / 2 + 1;
30             //比较右值，如果>，则right更新
31             if(nums[mid] > target) {
32                 right = mid - 1;
33             }
34             //修改Left
35             else {
36                 left = mid;
37             }
38         }
39         res[1] = right;
40         return res;
41     }

View Code