Binary search simplified

class Main {

public static void main(String[] args) {

//refer https://medium.com/@elizarov/programming-binary-search-6e999783ba5d

//refer https://www.geeksforgeeks.org/variants-of-binary-search/

//refer https://repl.it/@dharmendratolan/GoodnaturedPertinentIntegrationtesting

// java signed and unsigned right shift

int test = Integer.MAX_VALUE;

System.out.println(test);

int t1 = test + 1;

System.out.println(t1);

int t2 = (test + test) >>> 1;

System.out.println(t2);

int t3 = (test + test) >> 1;

System.out.println(t3);

int[] a = {3,3,3,20,20,20};

int k = 3;

k = 3;

System.out.println("any(" + k + ")" + any(a,k));

k = 4;

System.out.println("any(" + k + ")" + any(a,k));

k = 20;

System.out.println("any(" + k + ")" + any(a,k));

k = 3;

System.out.println("firstGte(" + k + ")" + firstGte(a,k));

k = 20;

System.out.println("firstGte(" + k + ")" + firstGte(a,k));

k = 19;

System.out.println("firstGte(" + k + ")" + firstGte(a,k));

k = 21;

System.out.println("firstGte(" + k + ")" + firstGte(a,k));

k = 3;

System.out.println("firstGt(" + k + ")" + firstGt(a,k));

k = 20;

System.out.println("firstGt(" + k + ")" + firstGt(a,k));

k = 19;

System.out.println("firstGt(" + k + ")" + firstGt(a,k));

k = 3;

System.out.println("lastLte(" + k + ")" + lastLte(a,k));

k = 20;

System.out.println("lastLte(" + k + ")" + lastLte(a,k));

k = 19;

System.out.println("lastLte(" + k + ")" + lastLte(a,k));

k = 3;

System.out.println("lastLt(" + k + ")" + lastLt(a,k));

k = 20;

System.out.println("lastLt(" + k + ")" + lastLt(a,k));

k = 19;

System.out.println("lastLt(" + k + ")" + lastLt(a,k));

k = 21;

System.out.println("lastLt(" + k + ")" + lastLt(a,k));

}

private static Integer lastLt(int[] a, int k) {

// last LT means the element just at the left of k(or virtual k)

int l = -1;

int r = a.length;

Integer ans = null;

while(r > l + 1) { // r - l will overflow if r = Int.MAX and l = -1

int m = (r+l) >>> 1; // r + l will overflow if r = Int.Max and l > 0

//System.out.println("in " + l +" " + r +" " +m);

if(a[m] < k) {

l = m;

} else {

r = m;

}

//System.out.println("out " + l +" " + r +" " +m);

}

return l;

}

private static Integer lastLte(int[] a, int k) {

// last LTE means (the last k) or (element just left of virtual k)

int l = -1;

int r = a.length;

Integer ans = null;

while(r > l + 1) { // r - l will overflow if r = Int.MAX and l = -1

int m = (r+l) >>> 1; // r + l will overflow if r = Int.Max and l > 0

//System.out.println("in " + l +" " + r +" " +m);

if(a[m] <= k) {

l = m;

} else {

r = m;

}

//System.out.println("out " + l +" " + r +" " +m);

}

return l;

}

private static Integer firstGt(int[] a, int k) {

//firstGt means the element just right of k (or virtual k)

int l = -1;

int r = a.length;

Integer ans = null;

while(r > l + 1) { // r - l will overflow if r = Int.MAX and l = -1

int m = (r+l) >>> 1; // r + l will overflow if r = Int.Max and l > 0

//System.out.println("in " + l +" " + r +" " +m);

if(a[m] > k) {

r = m;

} else {

l = m;

}

//System.out.println("out " + l +" " + r +" " +m);

}

return r;

}

private static Integer firstGte(int[] a, int k) {

//firstGte means (the first k) or (the element just right of virtual k)

int l = -1;

int r = a.length;

//exact match

Integer ans = null;

while(r > l + 1) { // r - l will overflow if r = Int.MAX and l = -1

int m = (r+l) >>> 1; // r + l will overflow if r = Int.Max and l > 0

//System.out.println("in " + l +" " + r +" " +m);

if(a[m] >= k) {

r = m;

} else {

l = m;

}

//System.out.println("out " + l +" " + r +" " +m);

}

return r;

}

private static Integer any(int[] a, int k) {

int l = -1;

int r = a.length;

//exact match

Integer ans = null;

while(r > l + 1) { // r - l will overflow if r = Int.MAX and l = -1

int m = (r+l) >>> 1; // r + l will overflow if r = Int.Max and l > 0

//System.out.println("in " + l +" " + r +" " +m);

if(a[m] == k) {

ans = m; break;

}

else if(a[m] > k) {

r = m;

} else {

l = m;

}

//System.out.println("out " + l +" " + r +" " +m);

}

return ans;

}

}