Java recursive solution search two halfs only when necessary


  • 0
    R

    This is a recursive solution, which search both two halfs only when necessary.

    public class Solution {
        private int[] searchRangeHelper(int[] a, int start, int end, int target) {
            int mid;
            int[] res = new int[] {-1, -1}, temp;
            if(start == end) {
                if(a[start] == target) {
                    res[0] = start;
                    res[1] = end;
                }
            } else if(start < end) {
                if(a[start] == target && a[end] == target) {
                    res[0] = start;
                    res[1] = end;
                } else {
                    mid = start + (end - start) / 2;
                    if(a[mid] == target) {
                        res[0] = mid;
                        res[1] = mid;
                        temp = searchRangeHelper(a, start, mid - 1, target);
                        if(temp[0] != -1) {
                            res[0] = temp[0];
                        }
                        temp = searchRangeHelper(a, mid + 1, end, target);
                        if(temp[1] != -1) {
                            res[1] = temp[1];
                        }
                    } else if(a[mid] > target) {
                        res = searchRangeHelper(a, start, mid - 1, target);
                    } else if(a[mid] < target) {
                        res = searchRangeHelper(a, mid + 1, end, target);
                    }
                }
            }
            
            return res;
        }
        public int[] searchRange(int[] nums, int target) {
            return searchRangeHelper(nums, 0, nums.length - 1, target);
        }
    }
    

Log in to reply
 

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