In the previous lab, we developed test cases for three array search algorithms.
This time we are going to implement those algorithms as methods of a class called
Search.
You may reuse the IntelliJ project from last time.
Create file src/Search.java which contains a public class called Search.
When your lab is complete, submit your Search.java file to Autograder.
By the way, make sure to test your solutions locally using the test cases from Lab 1 first!
Implement the search function find_first_true that finds
the position of the first true in array A of boolean values,
that is, find the smallest index i such that A[i] is true.
The search is restricted to the subarray within A that starts at the begin
index and finishes one element before the end index
(half-open interval [begin,end)).
If there are no true elements in the subarray, then find_first_true
returns the end position of the subarray.
The caller of find_first_true always provides a valid half-open
range: begin <= end, 0 <= begin, begin <= A.length,
0 <= end, and end <= A.length.
The time it takes for your algorithm to run should be proportional to the
length of the array A.
[Example 1] If the input array A is
{false, false, true, false, true}
then the result should be 2 because A[2] == true and there are no
true elements at lower indices (A[0] and A[1] are both false).
[Example 2] Suppose A is the array
{true, false, true, false, true}
and we search in the half-open interval [1,3). The answer should be 2.
find_first_true(A, 1, 3) == 2
Add the following method to the Search class and fill-in the
implementation:
public static int find_first_true(boolean[] A, int begin, int end) {
// ...
}
⚠️ Use find_first_true to implement the function find_first_equal
that searches on an array of integers, with the goal of finding the
position of the first element that is equal to the x parameter.
If there are no elements equal to x, the length of the array is returned.
Again, the time it takes for your algorithm to run should be proportional
to the length of A.
[Example 3] Suppose A is the array
{32, 11, 4, 5, 99, 5, 32, 75}
then the result of search for 5 should be 3:
find_first_equal(A, 5) == 3
Implement the following method in the Search class:
public static int find_first_equal(int[] A, int x) {
// ...
}
Similar to Problem 1, we search on an array of booleans and look for the position
of the first true. This time we suppose that all of the false elements in the array
come before all of the true elements (sorted).
Implement find_first_true_sorted(A, begin, end), which returns
the position of the first true in array A, that is, it finds the
smallest index i greater or equal to begin and less than end
such that A[i] is true. If there is no true within the
half-open range [begin,end), it returns end. The caller always supplies a
valid half-open range which means begin <= end, 0 <= begin,
begin <= A.length, 0 <= end, and end <= A.length. Furthermore,
the caller also ensures that A must already be sorted, so that all the false
elements come before any true elements.
The algorithm should be more efficient and runs in time proportional to the ⚠️logarithm of the length of the array, by looking at the element in the middle and restricting the search to the right or left subarray depending on its value.
[Example 4] Suppose A is the sorted array
{false, false, true, true, true, true, true}
The position of the first true element is 2 in this case.
Implement your algorithm in the following method of the Search class.
Again, restrict your search to the half-open interval [begin,end):
public static int find_first_true_sorted(boolean[] A, int begin, int end) {
// ...
}