Easy and clear Java Binary search solution


  • 0
    S
    public class Solution {
        public int[] searchRange(int[] nums, int target) {
          int start = 0, end = nums.length - 1, mid = -1;
          boolean found = false;
          while (start <= end) {
            mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                found = true;
                break;
            }
            else if (nums[mid] < target) start = mid + 1;
            else end = mid - 1;
          }
          
          // If not found
          if (!found) return new int[]{-1, -1};
          
          // Otherwise..
          // Find left
          int left = mid;
          while (left >= 0 && nums[left] == target) --left;
          // Find right
          int right = mid;
          while (right < nums.length && nums[right] == target) ++right;
          
          return new int[]{left + 1, right - 1};
        }
    }

  • 1
    Y

    I don't think the time complexity of this solution is O(log n)
    Because time complexity of your left and right finding process is kind of O(n);


Log in to reply
 

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