LeetCode OJ: 34. Search for a Range

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

題目連結,解法為從陣列左右兩邊各用Binary Search找一次。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1;
        int[] result = new int[] { -1, -1 };
    
        // The left boundary
        while (left < right)
        {
            int mid = (left + right) /2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        if (nums[left] != target) return result;
        else result[0] = left;
    
        // The right boundary
        right = n-1;
        while (left < right)
        {
            int mid = (left + right) / 2 + 1;
            if (nums[mid] > target) right = mid - 1;  
            else left = mid;
        }
        
        result[1] = right;
        return result;
    }
}

沒有留言: