Search a sorted array for first occurrence of k
BinarySearchFirstKTemplate.javapublic static int searchFirst(ArrayList<Integer> A, int k) {
int l = 0, r = A.size() - 1, res = -1;
while (l <= r) {
int m = l + ((r - l) >> 1);
if (A.get(m) > k) {
r = m - 1;
} else if (A.get(m) == k) {
// Record the solution and keep searching the left part.
res = m;
r = m - 1;
} else { // A.get(m) < k
l = m + 1;
}
}
return res;
}
Search a sorted array for the first element greater than~k
BinarySearchLargerKTemplate.java
public static int searchFirstLargerK(ArrayList<Integer> a, int k) {
int l = 0, r = a.size() - 1, res = -1;
while (l <= r) {
int m = l + ((r - l) >> 1);
if (a.get(m) > k) {
// Records the solution and keep searching the left part.
res = m;
r = m - 1;
} else { // A.get(m) <= k.
l = m + 1;
}
}
return res;
}
Search a sorted array for \mbox{A[i]=i}
BinarySearchAiEqI.java
public static int searchIndexValueEqual(ArrayList<Integer> A) {
int l = 0, r = A.size() - 1;
while (l <= r) {
int m = l + ((r - l) / 2);
int val = A.get(m) - m;
if (val == 0) {
return m;
} else if (val > 0) {
r = m - 1;
} else { // val < 0
l = m + 1;
}
}
return -1;
}
Search a cyclically sorted array
BinarySearchCircularArrayTemplate.java
public static int searchSmallest(ArrayList<Integer> A) {
int l = 0, r = A.size() - 1;
while (l < r) {
int m = l + ((r - l) >> 1);
if (A.get(m) > A.get(r)) {
l = m + 1;
} else { // A.get(m) <= A.get(r)
r = m;
}
}
return l;
}
BinarySearchCircularArrayWithDuplicatesTemplate.java
// @include
private static int searchSmallestHelper(ArrayList<Integer> A, int l, int r) {
if (l == r) {
return l;
}
int m = l + ((r - l) >> 1);
if (A.get(m) > A.get(r)) {
return searchSmallestHelper(A, m + 1, r);
} else if (A.get(m) < A.get(r)) {
return searchSmallestHelper(A, l, m);
} else { // A.get(m) == A.get(r)
// Smallest element must exist in either left or right side.
int lRes = searchSmallestHelper(A, l, m);
int rRes = searchSmallestHelper(A, m + 1, r);
return A.get(rRes) < A.get(lRes) ? rRes : lRes;
}
}
public static int searchSmallest(ArrayList<Integer> A) {
return searchSmallestHelper(A, 0, A.size() - 1);
}
Search a sorted array of unknown length
BinarySearchUnknownLengthTemplate.javapublic static int binarySearchUnknownLen(List<Integer> A, int k) {
// Find the possible range where k exists.
int p = 0;
while (true) {
try {
int val = A.get((1 << p) - 1);
if (val == k) {
return (1 << p) - 1;
} else if (val > k) {
break;
}
} catch (Exception e) {
break;
}
++p;
}
// Binary search between indices 2^(p - 1) and 2^p - 2.
// Need max below in case k is smaller than all entries
// in A, since p becomes 0.
int l = max(0, 1 << (p - 1)), r = (1 << p) - 2;
while (l <= r) {
int m = l + ((r - l) >> 1);
try {
int val = A.get(m);
if (val == k) {
return m;
} else if (val > k) {
r = m - 1;
} else { // A[m] < k
l = m + 1;
}
} catch (Exception e) {
r = m - 1; // search the left part if out of boundary.
}
}
return -1; // nothing matched k.
}
