Searching Flashcards
Binary Search
public static int bsearch(int t, List A){
int L = 0, U = A.size() - 1;
while(L <= U) {
int M = (L + U )/ 2;
if ( A.get(M) < t) {
L = M + 1;
} else if (A.get(M) == t){
return M;
}else {
U = M -1;
}
return -1;
}
}
To search an array use binarySearch function of ?
time O(log n)
Arrays
To search a sorted List-type object, use binarySearch of ?
Collections
returning index of the searched key or negative value if not found
Time Complexity of Search for 1) AttayList 2) Linked List
1) O(log n)
2) O(n)
What happens if there are multiple searched keys? in Arrays and Collections by Binary search
Neither of them guarantees which one will be found.
Write a method that takes a sorted array and a key and returns the index of the first occurrence of that key in the array. Return -1 if the key does not appear in the array.
Time O(log n)
public class SearchFirstKey {
@EpiTest(testDataFile = "search\_first\_key.tsv")
public static int searchFirstOfK(List A, int k) {
int left = 0, right = A.size() - 1, result = -1;
// A.subList(left, right + 1) is the candidate set.
while (left \<= right) {
int mid = left + ((right - left) / 2);
if (A.get(mid) \> k) {
right = mid - 1;
} else if (A.get(mid) == k) {
result = mid;
// Nothing to the right of mid can be the first occurrence of k.
right = mid - 1;
} else { // A.get(mid) \< k
left = mid + 1;
}
}
return result;
}
Design an efficien algorithm that takes a sorted array of distinct integers and returns an index i such that the elment at index i equals i.
O(log n)
public static int searchEntryEqualToItsIndex(List A) {
int left = 0, right = A.size() - 1;
while (left \<= right) {
int mid = left + ((right - left) / 2);
int difference = A.get(mid) - mid;
// A.get(mid) == mid if and only if difference == 0.
if (difference == 0) {
return mid;
} else if (difference \> 0) {
right = mid - 1;
} else { // difference \< 0.
left = mid + 1;
}
}
return -1;
}
design an O(Log n ) algorithm for finding the position of the smallest in a cyclically sorted array. Assume all elements are distinct.
Time O(log n)
public static int searchSmallest(List A) {
int left = 0, right = A.size() - 1;
while (left \< right) {
int mid = left + ((right - left) / 2);
if (A.get(mid) \> A.get(right)) {
// Minimum must be in A.subList(mid + 1, right + 1).
left = mid + 1;
} else { // A.get(mid) \< A.get(right).
// Minimum cannot be in A.subList(mid + 1, right + 1) so it must be in
// A.sublist(left, mid + 1).
right = mid;
}
}
// Loop ends when left == right.
return left;
}
Write a progam which takes a nonnegative integer and returns the largest integer whose square is less than or equal to the given integer.
Time O(log k)
public class IntSquareRoot {
@EpiTest(testDataFile = "int\_square\_root.tsv")
public static int squareRoot(int k) {
long left = 0, right = k;
// Candidate interval [left, right] where everything before left has
// square \<= k, and everything after right has square \> k.
while (left \<= right) {
long mid = left + ((right - left) / 2);
long midSquared = mid \* mid;
if (midSquared \<= k) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return (int)left - 1;
}
Implement a function which takes as input a floating point value and returns its square root.
Time O(log x/s)
public class RealSquareRoot {
@EpiTest(testDataFile = "real\_square\_root.tsv")
public static double squareRoot(double x) {
// Decides the search range according to x's value relative to 1.0.
double left, right;
if (x \< 1.0) {
left = x;
right = 1.0;
} else { // x \>= 1.0.
left = 1.0;
right = x;
}
// Keeps searching as long as left != right, within tolerance.
while (compare(left, right) != Ordering.EQUAL) {
double mid = left + 0.5 \* (right - left);
double midSquared = mid \* mid;
if (compare(midSquared, x) == Ordering.LARGER) {
right = mid;
} else {
left = mid;
}
}
return left;
}
private enum Ordering { SMALLER, EQUAL, LARGER }
private static Ordering compare(double a, double b) {
final double EPSILON = 0.000001;
// Uses normalization for precision problem.
double diff = (a - b) / Math.max(Math.abs(a), Math.abs(b));
return diff \< -EPSILON
? Ordering.SMALLER
: (diff \> EPSILON ? Ordering.LARGER : Ordering.EQUAL);
}
Design an algorithm that takes a 2D sorted array and a number and checks whether that number appeares in the array.
Time O(m + n)
public class SearchRowColSortedMatrix {
@EpiTest(testDataFile = "search\_row\_col\_sorted\_matrix.tsv")
public static boolean matrixSearch(List> A, int x) {
int row = 0, col = A.get(0).size() - 1; // Start from the top-right corner.
// Keeps searching while there are unclassified rows and columns.
while (row \< A.size() && col \>= 0) {
if (A.get(row).get(col).equals(x)) {
return true;
} else if (A.get(row).get(col) \< x) {
\++row; // Eliminate this row.
} else { // A.get(row).get(col) \> x.
--col; // Eliminate this column.
}
}
return false;
}
Design an algorithm to find the min and max elements in an array.
Time O(n)
Space O(1)
public static class MinMax {
public Integer smallest;
public Integer largest;
public MinMax(Integer smallest, Integer largest) {
this.smallest = smallest;
this.largest = largest;
}
private static MinMax minMax(Integer a, Integer b) {
return Integer.compare(b, a) \< 0 ? new MinMax(b, a) : new MinMax(a, b);
}
public static MinMax findMinMax(List A) {
if (A.size() \<= 1) {
return new MinMax(A.get(0), A.get(0));
}
MinMax globalMinMax = MinMax.minMax(A.get(0), A.get(1));
// Process two elements at a time.
for (int i = 2; i + 1 \< A.size(); i += 2) {
MinMax localMinMax = MinMax.minMax(A.get(i), A.get(i + 1));
globalMinMax =
new MinMax(Math.min(globalMinMax.smallest, localMinMax.smallest),
Math.max(globalMinMax.largest, localMinMax.largest));
}
// If there is odd number of elements in the array, we still
// need to compare the last element with the existing answer.
if ((A.size() % 2) != 0) {
globalMinMax =
new MinMax(Math.min(globalMinMax.smallest, A.get(A.size() - 1)),
Math.max(globalMinMax.largest, A.get(A.size() - 1)));
}
return globalMinMax;
}
Design an algorithm for computing the kth largest element in an array. Assume entries are distinct.
Time O(n)
public static int findKthLargest(int k, List A) {
return findKth(A, k, (a, b) -\> Integer.compare(b, a)); }
// The numbering starts from one, i.e., if A = [3,1,-1,2] then
// findKthSmallest(1, A) returns -1, findKthSmallest(2, A) returns 1,
// findKthSmallest(3, A) returns 2, and findKthSmallest(4, A) returns 3.
public static int findKthSmallest(int k, List A) {
return findKth(A, k, (a, b) -\> Integer.compare(a, b));
}
public static int findKth(List A, int k, Comparator cmp) {
int left = 0, right = A.size() - 1;
Random r = new Random(0);
while (left \<= right) {
// Generates a random integer in [left, right].
int pivotIdx = r.nextInt(right - left + 1) + left;
int newPivotIdx = partitionAroundPivot(left, right, pivotIdx, A, cmp);
if (newPivotIdx == k - 1) {
return A.get(newPivotIdx);
} else if (newPivotIdx \> k - 1) {
right = newPivotIdx - 1;
} else { // newPivotIdx \< k - 1.
left = newPivotIdx + 1;
}
}
throw new NoSuchElementException("no k-th node in array A");
}
// Partitions A.subList(left, right+1) around pivotIdx, returns the new index
// of the pivot, newPivotIdx, after partition. After partitioning,
// A.subList(left, newPivotIdx) contains elements that are "greater than" the
// pivot, and A.subList(newPivotIdx + 1 , right + 1) contains elements that
// are "less than" the pivot.
//
// Note: "greater than" and "less than" are defined by the Comparator object.
//
// Returns the new index of the pivot element after partition.
private static int partitionAroundPivot(int left, int right, int pivotIdx,
List A,
Comparator cmp) {
int pivotValue = A.get(pivotIdx);
int newPivotIdx = left;
Collections.swap(A, pivotIdx, right);
for (int i = left; i < right; ++i) {
if (cmp.compare(A.get(i), pivotValue) < 0) {
Collections.swap(A, i, newPivotIdx++);
}
}
Collections.swap(A, right, newPivotIdx);
return newPivotIdx;
}
Find missing IP address.
Suppose you were given a file containing roughly one billion IP addresses, each of which is a 32 bit quantity. How would you programmatically find an IP address that is not in the file? unlimited drive space with only a few megabytes of RAM.
Space depends on the count array
public static int findMissingElement(Iterable stream) {
final int NUM_BUCKET = 1 << 16;
int[] counter = new int[NUM_BUCKET];
Iterator s = stream.iterator();
while (s.hasNext()) {
int d = s.next();
int idx = d >>> 16;
}
// Look for a bucket that contains less than (1 \<\< 16) elements. final int BUCKET\_CAPACITY = 1 \<\< 16;
int candidateBucket = 0;
for (int i = 0; i < NUM_BUCKET; ++i) {
if (counter[i] < BUCKET_CAPACITY) {
candidateBucket = i;
break;
}
}
// Finds all IP addresses in the stream whose first 16 bits
// are equal to candidateBucket.
BitSet candidates = new BitSet(BUCKET\_CAPACITY);
s = stream.iterator(); // Search from the beginning again.
while (s.hasNext()) {
int x = s.next();
if (candidateBucket == upperPartX) {
// Records the presence of 16 LSB of x.
int lowerPartX = ((1 \<\< 16) - 1) & x;
candidates.set(lowerPartX);
}
}
for (int i = 0; i < BUCKET_CAPACITY; ++i) {
if (!candidates.get(i)) {
int e = (candidateBucket << 16) | i;
return e;
}
}
throw new IllegalArgumentException("no missing element");
}
Find the duplicate and missing elements
You are given an array of n integers, each between 0 and n-1, inclusive. Exactly one element appears twice, implying that exactly one number between 0 and n-1 is missing from the array.
public static class DuplicateAndMissing {
public Integer duplicate;
public Integer missing;
public DuplicateAndMissing(Integer duplicate, Integer missing) {
this.duplicate = duplicate;
this.missing = missing;
}
}
public static DuplicateAndMissing findDuplicateMissing(List A) {
// Compute the XOR of all numbers from 0 to |A| - 1 and all entries in A.
int missXorDup = 0;
for (int i = 0; i \< A.size(); ++i) {
missXorDup ^= i ^ A.get(i);
}
// We need to find a bit that's set to 1 in missXorDup. Such a bit
// must exist if there is a single missing number and a single duplicated
// number in A.
//
// The bit-fiddling assignment below sets all of bits in differBit to 0
// except for the least significant bit in missXorDup that's 1.
int differBit = missXorDup & (~(missXorDup - 1));
int missOrDup = 0;
for (int i = 0; i \< A.size(); ++i) {
// Focus on entries and numbers in which the differBit-th bit is 1.
if ((i & differBit) != 0) {
missOrDup ^= i;
}
if ((A.get(i) & differBit) != 0) {
missOrDup ^= A.get(i);
}
}
// missOrDup is either the missing value or the duplicated entry. If // missOrDup is in A, missOrDup is the duplicate; otherwise, missOrDup is // the missing value. return A.contains(missOrDup) ? new DuplicateAndMissing(missOrDup, missOrDup ^ missXorDup) : new DuplicateAndMissing(missOrDup ^ missXorDup, missOrDup); }
