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]
.
The variation of traditional binary search. In order to be consisted with the version of binary search I'm most comfortable with, I used one kinds of the implementation that is most similar with the original one to find the first occurrence and the last occurrence . There are many other ways of implementing the functionality and you need only to recite one of them.
public class Solution { public int[] searchRange(int[] A, int target) { int[] res = new int[2]; res[0] = left(A, target); res[1] = right(A, target); return res; } private int left(int[] A, int target) { int l = 0, r = A.length-1, result = -1; while(l <= r) { int mid = l + (r - l) / 2; if(A[mid] == target) { result = mid; r = mid - 1; } else if(A[mid] > target) r = mid - 1; else l = mid + 1; } return result; } private int right(int[] A, int target) { int l = 0, r = A.length-1, result = -1; while(l <= r) { int mid = l + (r - l) / 2; if(A[mid] == target) { result = mid; l = mid + 1; } else if(A[mid] > target) r = mid - 1; else l = mid + 1; } return result; } }
没有评论:
发表评论