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 }



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