Skip to content

Commit baa1ddb

Browse files
kunal-kushwahakunal-kushwaha
committed
bs questions
1 parent fb5439e commit baa1ddb

File tree

11 files changed

+519
-0
lines changed

11 files changed

+519
-0
lines changed

‎lectures/10-binary search/Binary Search - Questions.pdf

2.99 MB
Binary file not shown.

‎lectures/10-binary search/code/src/com/kunal/Ceiling.java

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package com.kunal;
2+
3+
public class Ceiling {
4+
5+
public static void main(String[] args) {
6+
int[] arr = {2, 3, 5, 9, 14, 16, 18};
7+
int target = 15;
8+
int ans = ceiling(arr, target);
9+
System.out.println(ans);
10+
}
11+
12+
// return the index of smallest no >= target
13+
static int ceiling(int[] arr, int target) {
14+
15+
// but what if the target is greater than the greatest number in the array
16+
if (target > arr[arr.length - 1]) {
17+
return -1;
18+
}
19+
int start = 0;
20+
int end = arr.length - 1;
21+
22+
while(start <= end) {
23+
// find the middle element
24+
// int mid = (start + end) / 2; // might be possible that (start + end) exceeds the range of int in java
25+
int mid = start + (end - start) / 2;
26+
27+
if (target < arr[mid]) {
28+
end = mid - 1;
29+
} else if (target > arr[mid]) {
30+
start = mid + 1;
31+
} else {
32+
// ans found
33+
return mid;
34+
}
35+
}
36+
return start;
37+
}
38+
}

‎lectures/10-binary search/code/src/com/kunal/FirstAndLastPosition.java

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package com.kunal;
2+
3+
public class FirstAndLastPosition {
4+
public static void main(String[] args) {
5+
6+
}
7+
8+
public int[] searchRange(int[] nums, int target) {
9+
10+
int[] ans = {-1, -1};
11+
// check for first occurrence if target first
12+
ans[0] = search(nums, target, true);
13+
if (ans[0] != -1) {
14+
ans[1] = search(nums, target, false);
15+
}
16+
return ans;
17+
}
18+
19+
// this function just returns the index value of target
20+
int search(int[] nums, int target, boolean findStartIndex) {
21+
int ans = -1;
22+
int start = 0;
23+
int end = nums.length - 1;
24+
while(start <= end) {
25+
// find the middle element
26+
// int mid = (start + end) / 2; // might be possible that (start + end) exceeds the range of int in java
27+
int mid = start + (end - start) / 2;
28+
29+
if (target < nums[mid]) {
30+
end = mid - 1;
31+
} else if (target > nums[mid]) {
32+
start = mid + 1;
33+
} else {
34+
// potential ans found
35+
ans = mid;
36+
if (findStartIndex) {
37+
end = mid - 1;
38+
} else {
39+
start = mid + 1;
40+
}
41+
}
42+
}
43+
return ans;
44+
}
45+
}

‎lectures/10-binary search/code/src/com/kunal/Floor.java

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package com.kunal;
2+
3+
public class Floor {
4+
5+
public static void main(String[] args) {
6+
int[] arr = {2, 3, 5, 9, 14, 16, 18};
7+
int target = 1;
8+
int ans = floor(arr, target);
9+
System.out.println(ans);
10+
}
11+
12+
// return the index: greatest number <= target
13+
static int floor(int[] arr, int target) {
14+
int start = 0;
15+
int end = arr.length - 1;
16+
17+
while(start <= end) {
18+
// find the middle element
19+
// int mid = (start + end) / 2; // might be possible that (start + end) exceeds the range of int in java
20+
int mid = start + (end - start) / 2;
21+
22+
if (target < arr[mid]) {
23+
end = mid - 1;
24+
} else if (target > arr[mid]) {
25+
start = mid + 1;
26+
} else {
27+
// ans found
28+
return mid;
29+
}
30+
}
31+
return end;
32+
}
33+
}

‎lectures/10-binary search/code/src/com/kunal/InfiniteArray.java

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package com.kunal;
2+
// https://www.geeksforgeeks.org/find-position-element-sorted-array-infinite-numbers/
3+
public class InfiniteArray {
4+
public static void main(String[] args) {
5+
int[] arr = {3, 5, 7, 9, 10, 90,
6+
100, 130, 140, 160, 170};
7+
int target = 10;
8+
System.out.println(ans(arr, target));
9+
}
10+
static int ans(int[] arr, int target) {
11+
// first find the range
12+
// first start with a box of size 2
13+
int start = 0;
14+
int end = 1;
15+
16+
// condition for the target to lie in the range
17+
while (target > arr[end]) {
18+
int temp = end + 1; // this is my new start
19+
// double the box value
20+
// end = previous end + sizeofbox*2
21+
end = end + (end - start + 1) * 2;
22+
start = temp;
23+
}
24+
return binarySearch(arr, target, start, end);
25+
26+
}
27+
static int binarySearch(int[] arr, int target, int start, int end) {
28+
while(start <= end) {
29+
// find the middle element
30+
// int mid = (start + end) / 2; // might be possible that (start + end) exceeds the range of int in java
31+
int mid = start + (end - start) / 2;
32+
33+
if (target < arr[mid]) {
34+
end = mid - 1;
35+
} else if (target > arr[mid]) {
36+
start = mid + 1;
37+
} else {
38+
// ans found
39+
return mid;
40+
}
41+
}
42+
return -1;
43+
}
44+
}

‎lectures/10-binary search/code/src/com/kunal/Mountain.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package com.kunal;
2+
3+
public class Mountain {
4+
public static void main(String[] args) {
5+
6+
}
7+
// https://leetcode.com/problems/peak-index-in-a-mountain-array/
8+
// https://leetcode.com/problems/find-peak-element/
9+
public int peakIndexInMountainArray(int[] arr) {
10+
int start = 0;
11+
int end = arr.length - 1;
12+
13+
while (start < end) {
14+
int mid = start + (end - start) / 2;
15+
if (arr[mid] > arr[mid+1]) {
16+
// you are in dec part of array
17+
// this may be the ans, but look at left
18+
// this is why end != mid - 1
19+
end = mid;
20+
} else {
21+
// you are in asc part of array
22+
start = mid + 1; // because we know that mid+1 element > mid element
23+
}
24+
}
25+
// in the end, start == end and pointing to the largest number because of the 2 checks above
26+
// start and end are always trying to find max element in the above 2 checks
27+
// hence, when they are pointing to just one element, that is the max one because that is what the checks say
28+
// more elaboration: at every point of time for start and end, they have the best possible answer till that time
29+
// and if we are saying that only one item is remaining, hence cuz of above line that is the best possible ans
30+
return start; // or return end as both are =
31+
}
32+
}

‎lectures/10-binary search/code/src/com/kunal/RBS.java

Lines changed: 109 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,109 @@
1+
package com.kunal;
2+
// https://leetcode.com/problems/search-in-rotated-sorted-array/submissions/
3+
public class RBS {
4+
public static void main(String[] args) {
5+
int[] arr = {4,5,6,7,0,1,2};
6+
System.out.println(findPivot(arr));
7+
}
8+
9+
static int search(int[] nums, int target) {
10+
int pivot = findPivot(nums);
11+
12+
// if you did not find a pivot, it means the array is not rotated
13+
if (pivot == -1) {
14+
// just do normal binary search
15+
return binarySearch(nums, target, 0 , nums.length - 1);
16+
}
17+
18+
// if pivot is found, you have found 2 asc sorted arrays
19+
if (nums[pivot] == target) {
20+
return pivot;
21+
}
22+
23+
if (target >= nums[0]) {
24+
return binarySearch(nums, target, 0, pivot - 1);
25+
}
26+
27+
return binarySearch(nums, target, pivot + 1, nums.length - 1);
28+
}
29+
30+
static int binarySearch(int[] arr, int target, int start, int end) {
31+
while(start <= end) {
32+
// find the middle element
33+
// int mid = (start + end) / 2; // might be possible that (start + end) exceeds the range of int in java
34+
int mid = start + (end - start) / 2;
35+
36+
if (target < arr[mid]) {
37+
end = mid - 1;
38+
} else if (target > arr[mid]) {
39+
start = mid + 1;
40+
} else {
41+
// ans found
42+
return mid;
43+
}
44+
}
45+
return -1;
46+
}
47+
48+
// this will not work in duplicate values
49+
static int findPivot(int[] arr) {
50+
int start = 0;
51+
int end = arr.length - 1;
52+
while (start <= end) {
53+
int mid = start + (end - start) / 2;
54+
// 4 cases over here
55+
if (mid < end && arr[mid] > arr[mid + 1]) {
56+
return mid;
57+
}
58+
if (mid > start && arr[mid] < arr[mid - 1]) {
59+
return mid-1;
60+
}
61+
if (arr[mid] <= arr[start]) {
62+
end = mid - 1;
63+
} else {
64+
start = mid + 1;
65+
}
66+
}
67+
return -1;
68+
}
69+
70+
static int findPivotWithDuplicates(int[] arr) {
71+
int start = 0;
72+
int end = arr.length - 1;
73+
while (start <= end) {
74+
int mid = start + (end - start) / 2;
75+
// 4 cases over here
76+
if (mid < end && arr[mid] > arr[mid + 1]) {
77+
return mid;
78+
}
79+
if (mid > start && arr[mid] < arr[mid - 1]) {
80+
return mid-1;
81+
}
82+
83+
// if elements at middle, start, end are equal then just skip the duplicates
84+
if (arr[mid] == arr[start] && arr[mid] == arr[end]) {
85+
// skip the duplicates
86+
// NOTE: what if these elements at start and end were the pivot??
87+
// check if start is pivot
88+
if (arr[start] > arr[start + 1]) {
89+
return start;
90+
}
91+
start++;
92+
93+
// check whether end is pivot
94+
if (arr[end] < arr[end - 1]) {
95+
return end - 1;
96+
}
97+
end--;
98+
}
99+
// left side is sorted, so pivot should be in right
100+
else if(arr[start] < arr[mid] || (arr[start] == arr[mid] && arr[mid] > arr[end])) {
101+
start = mid + 1;
102+
} else {
103+
end = mid - 1;
104+
}
105+
}
106+
return -1;
107+
}
108+
109+
}

‎lectures/10-binary search/code/src/com/kunal/RotationCount.java

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
package com.kunal;
2+
3+
public class RotationCount {
4+
public static void main(String[] args) {
5+
int[] arr = {4,5,6,7,0,1,2};
6+
System.out.println(countRotations(arr));
7+
}
8+
9+
private static int countRotations(int[] arr) {
10+
int pivot = findPivot(arr);
11+
return pivot + 1;
12+
}
13+
14+
// use this for non duplicates
15+
static int findPivot(int[] arr) {
16+
int start = 0;
17+
int end = arr.length - 1;
18+
while (start <= end) {
19+
int mid = start + (end - start) / 2;
20+
// 4 cases over here
21+
if (mid < end && arr[mid] > arr[mid + 1]) {
22+
return mid;
23+
}
24+
if (mid > start && arr[mid] < arr[mid - 1]) {
25+
return mid-1;
26+
}
27+
if (arr[mid] <= arr[start]) {
28+
end = mid - 1;
29+
} else {
30+
start = mid + 1;
31+
}
32+
}
33+
return -1;
34+
}
35+
36+
// use this when arr contains duplicates
37+
static int findPivotWithDuplicates(int[] arr) {
38+
int start = 0;
39+
int end = arr.length - 1;
40+
while (start <= end) {
41+
int mid = start + (end - start) / 2;
42+
// 4 cases over here
43+
if (mid < end && arr[mid] > arr[mid + 1]) {
44+
return mid;
45+
}
46+
if (mid > start && arr[mid] < arr[mid - 1]) {
47+
return mid-1;
48+
}
49+
50+
// if elements at middle, start, end are equal then just skip the duplicates
51+
if (arr[mid] == arr[start] && arr[mid] == arr[end]) {
52+
// skip the duplicates
53+
// NOTE: what if these elements at start and end were the pivot??
54+
// check if start is pivot
55+
if (arr[start] > arr[start + 1]) {
56+
return start;
57+
}
58+
start++;
59+
60+
// check whether end is pivot
61+
if (arr[end] < arr[end - 1]) {
62+
return end - 1;
63+
}
64+
end--;
65+
}
66+
// left side is sorted, so pivot should be in right
67+
else if(arr[start] < arr[mid] || (arr[start] == arr[mid] && arr[mid] > arr[end])) {
68+
start = mid + 1;
69+
} else {
70+
end = mid - 1;
71+
}
72+
}
73+
return -1;
74+
}
75+
}

0 commit comments

Comments
 (0)