MARCH_DSA_BATCH/binarySearch.java at main · himanshubuyerteam/MARCH_DSA_BATCH · 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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
public class binarySearch {
    public boolean linearSearch(int []arr,int key)
    {
        for(int i=0;i<arr.length;i++)
        {
            if(arr[i]==key)
                return true;
        }
        return false;
    }
    public boolean binarySearch(int []arr,int key)
    {
        int s=0;
        int e=arr.length-1;
        while(s<=e)
        {
            int midIdx=(s+e)/2;
            int midVal=arr[midIdx];

            if(key==midVal)
                return true;
            else if(key>midVal) // Go to Right
                s=midIdx+1;
            else// Go to Left
                e=midIdx-1;
        }
        return false;
    }

    public int firstOcc(int []arr,int key)
    {
        int s=0;//start
        int e=arr.length-1;//end
        int ans=-1;
        while(s<=e)
        {
            int midIdx=(s+e)/2;
            int midVal =arr[midIdx];

            if(midVal == key)
            {
                ans=midIdx;
                if(midIdx==0 || arr[midIdx-1]!=key)
                    return ans;
                else
                    e=midIdx-1;
            }
            else if(midVal>key)//
                e=midIdx-1;
            else
                s=midIdx+1;
        }
        return ans;
    }

    public int LastOcc(int []arr,int key)
    {
        int s=0;//start
        int e=arr.length-1;//end
        int ans=-1;
        while(s<=e)
        {
            int midIdx=(s+e)/2;
            int midVal =arr[midIdx];
            if(midVal == key)
            {
                ans=midIdx;
                if(midIdx==arr.length-1 || arr[midIdx+1]!=key)
                    return ans;
                else
                    s=midIdx+1;
            }
            else if(midVal>key)//
                e=midIdx-1;
            else
                s=midIdx+1;
        }
        return ans;
    }

    public int countOcc(int []arr,int key)
    {
        int fo=firstOcc(arr,key);
        if(fo==-1)
            return 0;
        int lo=LastOcc(arr,key);
        return lo-fo+1;
    }


    //Array - RSA
    public int minElementInRSA(int []arr)
    {
        int s=0;
        int e=arr.length-1;
        while(s<e)
        {
            int midIdx = (s+e)/2;
            int midVal = arr[midIdx];
            if(midVal>arr[e])
                s=midIdx+1;
            else //midVal<arr[e]
                e=midIdx;
        }
        return arr[s];
    }
    public int no_of_rotation(int []arr)
    {
        int s=0;
        int e=arr.length-1;
        while(s<e)
        {
            int midIdx = (s+e)/2;
            int midVal = arr[midIdx];
            if(midVal>arr[e])
                s=midIdx+1;
            else //midVal<arr[e]
                e=midIdx;
        }
        return s;
    }


    public boolean possible(int []arr,int hr,int speed)
    {
        int hrused=0;
        for(int x:arr)
        {
            hrused+=Math.ceil(x/speed*1.0);
        }
        if(hrused>hr)
            return false;
        else
            return true;
    }
    public int koko(int []arr,int hr)
    {
        int s=1;
        int e=arr[0];
        for(int x:arr)
            e=Math.max(x,e);
        int ans=-1;
        while(s<e)
        {
            int speed=(s+e)/2;

            if(possible(arr,hr,speed)==true)
            {
                ans=speed;
                e=speed-1;
            }
            else
                s=speed+1;
        }
        return ans;
    }
}