Java simple solution O(log n), although with duplication


  • 0
    X

    Some solutions in the forum are not in O(log n) if there are a lot of duplications.
    This solution finds the lower index of occurrence and upper index of occurrence.
    Both in O(log n) although with duplications.

    public class Solution {
        public int[] searchRange(int[] nums, int target) {
            int[] results = new int[2];
            results[0] = lower(nums, target);
            results[1] = upper(nums, target);
            return results;
        }
        
        public int upper(int[] nums, int target) {
            int p1 = 0;
            int p2 = nums.length - 1;
            while(p1 < p2) {
                int mid = (p1 + p2 + 1) / 2;
                if (nums[mid] <= target) {
                    p1 = mid;
                } else {
                    p2 = mid - 1;
                }
            }
            if (nums[p1] != target) {
                return -1;
            } else {
                return p1;
            }
        }
        
        
        public int lower(int[] nums, int target) {
            int p1 = 0;
            int p2 = nums.length - 1;
            while(p1 < p2) {
                int mid = (p1 + p2) / 2;
                if (nums[mid] >= target) {
                    p2 = mid;
                } else {
                    p1 = mid + 1;
                }
            }
            if (nums[p1] != target) {
                return -1;
            } else {
                return p1;
            }
        }
    }
    

Log in to reply
 

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