Hi guys✋,This is day 14 of landing a Job in 30days👩💻.
This is the continuation of Day 13 blog .There are two implementation in binary search which is upper and lower bound.
import java.util.*;
public class LowerBound {
public static int lowerBound(int []arr, int n, int x) {
int low = 0, high = n - 1;
int ans = n;
while (low <= high) {
int mid = (low + high) / 2;
// maybe an answer
if (arr[mid] >= x) {
ans = mid;
//look for smaller index on the left
high = mid - 1;
} else {
low = mid + 1; // look on the right
}
}
return ans;
}
public static void main(String[] args) {
int[] arr = {3, 5, 8, 15, 19};
int n = 5, x = 9;
int ind = lowerBound(arr, n, x);
System.out.println("The lower bound is the index: " + ind);
}
}
import java.util.*;
public class UpperBound {
public static int upperBound(int[] arr, int x, int n) {
int low = 0, high = n - 1;
int ans = n;
while (low <= high) {
int mid = (low + high) / 2;
// maybe an answer
if (arr[mid] > x) {
ans = mid;
//look for smaller index on the left
high = mid - 1;
} else {
low = mid + 1; // look on the right
}
}
return ans;
}
public static void main(String[] args) {
int[] arr = {3, 5, 8, 9, 15, 19};
int n = 6, x = 9;
int ind = upperBound(arr, x, n);
System.out.println("The upper bound is the index: " + ind);
}
}
Binary problems:
https://github.com/kunal-kushwaha/DSA-Bootcamp-Java/blob/main/assignments/06-searching.md
Try to solve above problems