CodingInterviewQuestions/Leetcode/Leetcode Problem 34 Find First and Last Position of Element in Sorted Array.txt at master · akuchotrani/CodingInterviewQuestions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
34. Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]


Hint to solve: Perform 2 binary search to find first and last index.
Take care of the special case when during binary search the element at mid is equal to target and is not first or last index.


public class Solution
{
    public int BinarySearchRecursive(int[] nums, int target, int low, int high, bool isFirstIndex)
    {
        if(high < low)
            return -1;

        int mid = (low + high) / 2;

        if(isFirstIndex)
        {

            if((nums[mid] == target) && (mid == 0 || nums[mid-1] < nums[mid]))
            {
                return mid;
            }
            else if(nums[mid] < target)
            {
                return BinarySearchRecursive(nums, target, mid+1, high, isFirstIndex);
            }
            else
            {
                return BinarySearchRecursive(nums, target, low, mid-1, isFirstIndex);
            }
        }
        else
        {
            if((nums[mid] == target) && (mid == nums.Count() - 1 || nums[mid + 1] > target))
            {
                return mid;
            }
            else if(nums[mid]  > target)
            {
                return BinarySearchRecursive(nums, target, low, mid-1, isFirstIndex);
            }
            else
            {
                return BinarySearchRecursive(nums, target, mid+1, high, isFirstIndex);
            }
        }

    }


    private int BinarySearchIterative(int[] nums, int target, int low, int high, bool isFirstIndex)
    {
        int result = -1;
        while(true)
        {
            //Console.WriteLine(high + ","+ low);
            if(high < low)
                break;

            int mid = (low + high) / 2;
            if(isFirstIndex)
            {
                if((target == nums[mid]) && (mid == 0 || nums[mid-1] < target))
                {
                    return mid;
                }
                else if(nums[mid] >= target)
                {
                    high = mid - 1;
                }
                else
                {
                    low = mid + 1;
                }
            }
            else
            {
                if((target == nums[mid]) && (mid == nums.Count()-1 || nums[mid+1]> target))
                {
                    return mid;
                }
                else if(nums[mid] <= target)
                {
                    low = mid+1;
                }
                else
                {
                    high = mid-1;
                }
            }
        }

        return result;
    }

    public int[] SearchRange(int[] nums, int target)
    {
        int low = 0;
        int high = nums.Count() - 1;

        //last argument is a boolean that represents find the first index of a target number.
        int firstIndex = BinarySearchRecursive(nums, target, low, high, true);
        int lastIndex = BinarySearchRecursive(nums, target, low, high, false);
        // int firstIndex = BinarySearchIterative(nums, target, low, high, true);
        // int lastIndex = BinarySearchIterative(nums, target, low, high, false);

        int[] result = new int[]{firstIndex, lastIndex};

        return result;
    }
}