JavaWithDsa/Firstandlastoccurence.java at master · vishallovecode/JavaWithDsa · 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
package vishal2;

import java.util.Arrays;

public class firstAndLastoccurrence {
    public static int firstOcc(int array [] , int start , int end , int target) {
        int mid   = (start+end)/2;
        if(start>end) {
            return -1;
        }
        if(array[mid]==target && (mid==0 || array[mid-1]!=target)) {
            return mid;
        }
        else if(array[mid]>target) {
            return firstOcc(array ,start , mid-1, target );
        } else {
            return firstOcc(array ,mid+1 ,end , target );
        }


}
public static int lastOcc(int array [] , int start , int end , int target , int n) {
    int mid   = (start+end)/2;
    if(start>end) {
        return -1;
    }
    if(array[mid]==target && (mid==n-1 || array[mid+1] !=target)) {
        return mid;
    }
    else if(array[mid]>target) {
        return lastOcc(array ,start , mid-1, target ,n );
    } else {
        return lastOcc(array ,mid+1 ,end , target ,n );
    }


}
public static void main(String[] args) {
    int array[] = {1,2,3,4,5,5,5,5,6};
    int array1[] = {-1,-1};
    if(array.length==0) {
            System.out.println(Arrays.toString(array1));
    } else {
        int first  =  firstOcc(array, 0, array.length-1, 5);
        int lastOcc =  lastOcc(array, 0, array.length-1, 5, array.length);
        array1[0] = first;
        array1[1] = lastOcc;
        System.out.println(first + "" +lastOcc);
        // occurence of given element in sorted array
        int occurrence = lastOcc - first+1;
        System.out.println(Arrays.toString(array1) );
    }
}
}
package vishal2;

import java.util.Arrays;

public class firstAndLastoccurrence {
    public static int firstOcc(int array [] , int start , int end , int target) {
        int mid   = (start+end)/2;
        if(start>end) {
            return -1;
        }
        if(array[mid]==target && (mid==0 || array[mid-1]!=target)) {
            return mid;
        }
        else if(array[mid]>target) {
            return firstOcc(array ,start , mid-1, target );
        } else {
            return firstOcc(array ,mid+1 ,end , target );
        }


}
public static int lastOcc(int array [] , int start , int end , int target , int n) {
    int mid   = (start+end)/2;
    if(start>end) {
        return -1;
    }
    if(array[mid]==target && (mid==n-1 || array[mid+1] !=target)) {
        return mid;
    }
    else if(array[mid]>target) {
        return lastOcc(array ,start , mid-1, target ,n );
    } else {
        return lastOcc(array ,mid+1 ,end , target ,n );
    }


}
public static void main(String[] args) {
    int array[] = {1,2,3,4,5,5,5,5,6};
    int array1[] = {-1,-1};
    if(array.length==0) {
            System.out.println(Arrays.toString(array1));
    } else {
        int first  =  firstOcc(array, 0, array.length-1, 5);
        int lastOcc =  lastOcc(array, 0, array.length-1, 5, array.length);
        array1[0] = first;
        array1[1] = lastOcc;
        System.out.println(first + "" +lastOcc);
        // occurence of given element in sorted array
        int occurrence = lastOcc - first+1;
        System.out.println(Arrays.toString(array1) );
    }
}
}