Ruby Two Binary Search Solution


  • 0
    I

    First to find the first position of target, then the second position.

    Code:

    public class Solution {
        public int[] searchRange(int[] A, int target) {
            if (A == null || A.length == 0) {
                return new int[]{-1, -1};
            }
    
            int first = -1, last = -1;
    
            int start = 0, end = A.length-1, mid = -1;
    
            // search for first position
            while (start + 1 < end) {
                mid = start + (end - start) / 2;
    
                if (A[mid] >= target) {
                    end = mid;
                } else {
                    start = mid;
                }
    
                // System.out.printf("start: %d, mid: %d, end: %d\n", start, mid, end);
            }
    
            if (A[start] == target) {
                first = start;
            } else if (A[end] == target) {
                first = end;
            }
    
            start = 0; end = A.length - 1; mid = -1;
            // search for last position
    
            while (start + 1 < end) {
                mid = start + (end - start) / 2;
    
                if (A[mid] <= target) {
                    start = mid;
                } else {
                    end = mid;
                }
            }
    
            if (A[end] == target) {
                last = end;
            } else if (A[start] == target) {
                last = start;
            }
    
            return new int[] {first, last};
        }
    }
    
    

Log in to reply
 

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