Skip to content

Commit fb5439e

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

File tree

12 files changed

+252
-0
lines changed

12 files changed

+252
-0
lines changed

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

984 KB
Binary file not shown.

‎lectures/10-binary search/code/.idea/.gitignore

Lines changed: 3 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎lectures/10-binary search/code/.idea/description.html

Lines changed: 1 addition & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎lectures/10-binary search/code/.idea/encodings.xml

Lines changed: 6 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎lectures/10-binary search/code/.idea/misc.xml

Lines changed: 12 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎lectures/10-binary search/code/.idea/modules.xml

Lines changed: 8 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎lectures/10-binary search/code/.idea/project-template.xml

Lines changed: 3 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎lectures/10-binary search/code/.idea/uiDesigner.xml

Lines changed: 124 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎lectures/10-binary search/code/.idea/vcs.xml

Lines changed: 6 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎lectures/10-binary search/code/code.iml

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<module type="JAVA_MODULE" version="4">
3+
<component name="NewModuleRootManager" inherit-compiler-output="true">
4+
<exclude-output />
5+
<content url="file://$MODULE_DIR$">
6+
<sourceFolder url="file://$MODULE_DIR$/src" isTestSource="false" />
7+
</content>
8+
<orderEntry type="inheritedJdk" />
9+
<orderEntry type="sourceFolder" forTests="false" />
10+
</component>
11+
</module>

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

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

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

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package com.kunal;
2+
3+
public class OrderAgnosticBS {
4+
public static void main(String[] args) {
5+
// int[] arr = {-18, -12, -4, 0, 2, 3, 4, 15, 16, 18, 22, 45, 89};
6+
int[] arr = {99, 80, 75, 22, 11, 10, 5, 2, -3};
7+
int target = 22;
8+
int ans = orderAgnosticBS(arr, target);
9+
System.out.println(ans);
10+
}
11+
12+
static int orderAgnosticBS(int[] arr, int target) {
13+
int start = 0;
14+
int end = arr.length - 1;
15+
16+
// find whether the array is sorted in ascending or descending
17+
boolean isAsc = arr[start] < arr[end];
18+
19+
while(start <= end) {
20+
// find the middle element
21+
// int mid = (start + end) / 2; // might be possible that (start + end) exceeds the range of int in java
22+
int mid = start + (end - start) / 2;
23+
24+
if (arr[mid] == target) {
25+
return mid;
26+
}
27+
28+
if (isAsc) {
29+
if (target < arr[mid]) {
30+
end = mid - 1;
31+
} else {
32+
start = mid + 1;
33+
}
34+
} else {
35+
if (target > arr[mid]) {
36+
end = mid - 1;
37+
} else {
38+
start = mid + 1;
39+
}
40+
}
41+
}
42+
return -1;
43+
}
44+
}

0 commit comments

Comments
 (0)