} } }

    leetcode -- Search for a Range

    添加时间:2013-8-1 点击量:

    Given a sorted array of integers, find the starting and ending position of a given target value.


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


    思路:


    应用二分搜刮找到target的idx,然后查看该idx的阁下断定局限。


    算法错杂度:


    均匀景象下是O(lgn);


    最坏景象下数组中所有元素都雷同O(n);



     1 public class Solution {
    
    2 public int[] searchRange(int[] A, int target) {
    3 // Start typing your Java solution below
    4 // DO NOT write main() function
    5 int idx = binarySearch(A, target);
    6 int len = A.length;
    7 int[] results = null;
    8 if(idx == -1){
    9 results = new int[]{-1, -1};
    10 } else{
    11 int l = idx;
    12 int r = idx;
    13 while(l >= 0 && A[l] == target){
    14 l--;
    15 }
    16 l++;
    17
    18 while(r < len && A[r] == target){
    19 r++;
    20 }
    21 r--;
    22 results = new int[]{l, r};
    23 }
    24 return results;
    25 }
    26
    27 public int binarySearch(int[] A, int target){
    28 int len = A.length;
    29 int l = 0, r = len - 1;
    30 while(l <= r){
    31 int mid = (l + r) / 2;
    32 if(target == A[mid])
    33 return mid;
    34
    35 if(target > A[mid]){
    36 l = mid + 1;
    37 } else {
    38 r = mid - 1;
    39 }
    40 }
    41
    42 return -1;
    43 }
    44 }



    所有随风而逝的都属于昨天的,所有历经风雨留下来的才是面向未来的。—— 玛格丽特·米切尔 《飘》
    分享到: