AC solution using binary search in Java


  • 0
    L
    public class Solution {
    public int[] searchRange(int[] A, int target) {
        int[] invalid = new int[]{-1, -1};
        if (A == null || A.length == 0) return invalid;
        int lo = 0, hi = A.length - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >> 1;
            if (A[mid] >= target) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        if (lo < 0 || lo >= A.length || A[lo] != target) return invalid;
        int left = lo;
        hi = A.length - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >> 1;
            if (A[mid] <= target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        int right = hi;
        return new int[]{left, right};
    }
    

    }

    The trick is that you change the inequalities within the while loop to let lo and hi settle on the left and right of the range respectively.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.