Searching
Help Questions
AP Computer Science A › Searching
Which of the following implements a method named contains for searching an array sequentially, confirming whether or not the array contains a requested element?
public boolean contains(int[] arr, int val) {
for(int i = 0; i < arr.length; i++) {
if(arr[i] == val) {
return true;
}
}
return false;
}
public boolean contains(int[] arr, int val) {
for(int i = 0; i < arr.length; i++) {
if(arr[i] != val) {
return false;
}
}
return true;
}
public boolean contains(int[] arr, int val) {
boolean success;
for(int i = 0; i <= arr.length; i++) {
if(arr[i] == val) {
success = true;
} else {
success = false;
}
}
return success;
}
public int contains(int[] arr, int val) {
int success = -1;
for(int i = 0; i < arr.length; i++) {
if(arr[i] == val) {
success = val;
}
}
return success;
}
None of the other answers is correct
Explanation
The basic way to implement a sequential search is to test each element of an array until you match the value you want to find. All of these possible answers are very close to doing this. They all iterate through the given array. They all do check for the value. However, one option (with the if-else logic) could return false even if the element was found, for it continues to run after it is found. If another value does not match later in the array, the variable success will then be set to false. This will be returned, indicating failure to find the value. The integer-returning method seems to be fine, but it would be ambiguous if the value for the search is negative one. In this one case, this return value will not signal necessarily that it has been found—it could be just the "flag" indicating that nothing was found. Thus, the simplest method is the best here: return true as soon as it is found.
Which of the following implements a method named contains for searching an array sequentially, confirming whether or not the array contains a requested element?
public boolean contains(int[] arr, int val) {
for(int i = 0; i < arr.length; i++) {
if(arr[i] == val) {
return true;
}
}
return false;
}
public boolean contains(int[] arr, int val) {
for(int i = 0; i < arr.length; i++) {
if(arr[i] != val) {
return false;
}
}
return true;
}
public boolean contains(int[] arr, int val) {
boolean success;
for(int i = 0; i <= arr.length; i++) {
if(arr[i] == val) {
success = true;
} else {
success = false;
}
}
return success;
}
public int contains(int[] arr, int val) {
int success = -1;
for(int i = 0; i < arr.length; i++) {
if(arr[i] == val) {
success = val;
}
}
return success;
}
None of the other answers is correct
Explanation
The basic way to implement a sequential search is to test each element of an array until you match the value you want to find. All of these possible answers are very close to doing this. They all iterate through the given array. They all do check for the value. However, one option (with the if-else logic) could return false even if the element was found, for it continues to run after it is found. If another value does not match later in the array, the variable success will then be set to false. This will be returned, indicating failure to find the value. The integer-returning method seems to be fine, but it would be ambiguous if the value for the search is negative one. In this one case, this return value will not signal necessarily that it has been found—it could be just the "flag" indicating that nothing was found. Thus, the simplest method is the best here: return true as soon as it is found.
Which of the following implements a method named contains for searching an array sequentially, confirming whether or not the array contains a requested element?
public boolean contains(int[] arr, int val) {
for(int i = 0; i < arr.length; i++) {
if(arr[i] == val) {
return true;
}
}
return false;
}
public boolean contains(int[] arr, int val) {
for(int i = 0; i < arr.length; i++) {
if(arr[i] != val) {
return false;
}
}
return true;
}
public boolean contains(int[] arr, int val) {
boolean success;
for(int i = 0; i <= arr.length; i++) {
if(arr[i] == val) {
success = true;
} else {
success = false;
}
}
return success;
}
public int contains(int[] arr, int val) {
int success = -1;
for(int i = 0; i < arr.length; i++) {
if(arr[i] == val) {
success = val;
}
}
return success;
}
None of the other answers is correct
Explanation
The basic way to implement a sequential search is to test each element of an array until you match the value you want to find. All of these possible answers are very close to doing this. They all iterate through the given array. They all do check for the value. However, one option (with the if-else logic) could return false even if the element was found, for it continues to run after it is found. If another value does not match later in the array, the variable success will then be set to false. This will be returned, indicating failure to find the value. The integer-returning method seems to be fine, but it would be ambiguous if the value for the search is negative one. In this one case, this return value will not signal necessarily that it has been found—it could be just the "flag" indicating that nothing was found. Thus, the simplest method is the best here: return true as soon as it is found.
Which of the following implements a method named contains for searching an array sequentially, confirming whether or not the array contains a requested element?
public boolean contains(int[] arr, int val) {
for(int i = 0; i < arr.length; i++) {
if(arr[i] == val) {
return true;
}
}
return false;
}
public boolean contains(int[] arr, int val) {
for(int i = 0; i < arr.length; i++) {
if(arr[i] != val) {
return false;
}
}
return true;
}
public boolean contains(int[] arr, int val) {
boolean success;
for(int i = 0; i <= arr.length; i++) {
if(arr[i] == val) {
success = true;
} else {
success = false;
}
}
return success;
}
public int contains(int[] arr, int val) {
int success = -1;
for(int i = 0; i < arr.length; i++) {
if(arr[i] == val) {
success = val;
}
}
return success;
}
None of the other answers is correct
Explanation
The basic way to implement a sequential search is to test each element of an array until you match the value you want to find. All of these possible answers are very close to doing this. They all iterate through the given array. They all do check for the value. However, one option (with the if-else logic) could return false even if the element was found, for it continues to run after it is found. If another value does not match later in the array, the variable success will then be set to false. This will be returned, indicating failure to find the value. The integer-returning method seems to be fine, but it would be ambiguous if the value for the search is negative one. In this one case, this return value will not signal necessarily that it has been found—it could be just the "flag" indicating that nothing was found. Thus, the simplest method is the best here: return true as soon as it is found.
Which of the following implements a method named contains for searching an array sequentially, confirming whether or not the array contains a requested element?
public boolean contains(int[] arr, int val) {
for(int i = 0; i < arr.length; i++) {
if(arr[i] == val) {
return true;
}
}
return false;
}
public boolean contains(int[] arr, int val) {
for(int i = 0; i < arr.length; i++) {
if(arr[i] != val) {
return false;
}
}
return true;
}
public boolean contains(int[] arr, int val) {
boolean success;
for(int i = 0; i <= arr.length; i++) {
if(arr[i] == val) {
success = true;
} else {
success = false;
}
}
return success;
}
public int contains(int[] arr, int val) {
int success = -1;
for(int i = 0; i < arr.length; i++) {
if(arr[i] == val) {
success = val;
}
}
return success;
}
None of the other answers is correct
Explanation
The basic way to implement a sequential search is to test each element of an array until you match the value you want to find. All of these possible answers are very close to doing this. They all iterate through the given array. They all do check for the value. However, one option (with the if-else logic) could return false even if the element was found, for it continues to run after it is found. If another value does not match later in the array, the variable success will then be set to false. This will be returned, indicating failure to find the value. The integer-returning method seems to be fine, but it would be ambiguous if the value for the search is negative one. In this one case, this return value will not signal necessarily that it has been found—it could be just the "flag" indicating that nothing was found. Thus, the simplest method is the best here: return true as soon as it is found.
Which of the following implements a method named contains for searching an array sequentially, confirming whether or not the array contains a requested element?
public boolean contains(int[] arr, int val) {
for(int i = 0; i < arr.length; i++) {
if(arr[i] == val) {
return true;
}
}
return false;
}
public boolean contains(int[] arr, int val) {
for(int i = 0; i < arr.length; i++) {
if(arr[i] != val) {
return false;
}
}
return true;
}
public boolean contains(int[] arr, int val) {
boolean success;
for(int i = 0; i <= arr.length; i++) {
if(arr[i] == val) {
success = true;
} else {
success = false;
}
}
return success;
}
public int contains(int[] arr, int val) {
int success = -1;
for(int i = 0; i < arr.length; i++) {
if(arr[i] == val) {
success = val;
}
}
return success;
}
None of the other answers is correct
Explanation
The basic way to implement a sequential search is to test each element of an array until you match the value you want to find. All of these possible answers are very close to doing this. They all iterate through the given array. They all do check for the value. However, one option (with the if-else logic) could return false even if the element was found, for it continues to run after it is found. If another value does not match later in the array, the variable success will then be set to false. This will be returned, indicating failure to find the value. The integer-returning method seems to be fine, but it would be ambiguous if the value for the search is negative one. In this one case, this return value will not signal necessarily that it has been found—it could be just the "flag" indicating that nothing was found. Thus, the simplest method is the best here: return true as soon as it is found.
Which of the following implements a method named contains for searching an array sequentially, confirming whether or not the array contains a requested element?
public boolean contains(int[] arr, int val) {
for(int i = 0; i < arr.length; i++) {
if(arr[i] == val) {
return true;
}
}
return false;
}
public boolean contains(int[] arr, int val) {
for(int i = 0; i < arr.length; i++) {
if(arr[i] != val) {
return false;
}
}
return true;
}
public boolean contains(int[] arr, int val) {
boolean success;
for(int i = 0; i <= arr.length; i++) {
if(arr[i] == val) {
success = true;
} else {
success = false;
}
}
return success;
}
public int contains(int[] arr, int val) {
int success = -1;
for(int i = 0; i < arr.length; i++) {
if(arr[i] == val) {
success = val;
}
}
return success;
}
None of the other answers is correct
Explanation
The basic way to implement a sequential search is to test each element of an array until you match the value you want to find. All of these possible answers are very close to doing this. They all iterate through the given array. They all do check for the value. However, one option (with the if-else logic) could return false even if the element was found, for it continues to run after it is found. If another value does not match later in the array, the variable success will then be set to false. This will be returned, indicating failure to find the value. The integer-returning method seems to be fine, but it would be ambiguous if the value for the search is negative one. In this one case, this return value will not signal necessarily that it has been found—it could be just the "flag" indicating that nothing was found. Thus, the simplest method is the best here: return true as soon as it is found.
Which of the following implements a method named contains for searching an array sequentially, confirming whether or not the array contains a requested element?
public boolean contains(int[] arr, int val) {
for(int i = 0; i < arr.length; i++) {
if(arr[i] == val) {
return true;
}
}
return false;
}
public boolean contains(int[] arr, int val) {
for(int i = 0; i < arr.length; i++) {
if(arr[i] != val) {
return false;
}
}
return true;
}
public boolean contains(int[] arr, int val) {
boolean success;
for(int i = 0; i <= arr.length; i++) {
if(arr[i] == val) {
success = true;
} else {
success = false;
}
}
return success;
}
public int contains(int[] arr, int val) {
int success = -1;
for(int i = 0; i < arr.length; i++) {
if(arr[i] == val) {
success = val;
}
}
return success;
}
None of the other answers is correct
Explanation
The basic way to implement a sequential search is to test each element of an array until you match the value you want to find. All of these possible answers are very close to doing this. They all iterate through the given array. They all do check for the value. However, one option (with the if-else logic) could return false even if the element was found, for it continues to run after it is found. If another value does not match later in the array, the variable success will then be set to false. This will be returned, indicating failure to find the value. The integer-returning method seems to be fine, but it would be ambiguous if the value for the search is negative one. In this one case, this return value will not signal necessarily that it has been found—it could be just the "flag" indicating that nothing was found. Thus, the simplest method is the best here: return true as soon as it is found.
public static int foo(int\[\] arr, int x) {
int a = 0;
int b = arr.length - 1;
while(b >= a) {
int c = (a + b) / 2;
int v = arr\[c\];
if(v == x) {
return c;
} else if(v < x) {
a = c + 1;
} else {
b = c - 1;
}
}
return -1;
}
What is the value of y in the code below:
int\[\] vals = {1,3,4,5,6,31,41,51};
int x = 41;
int y = foo(vals,41);
6
6
41
41
-1
-1
5
5
7
7
Explanation
The first thing to notice in the code for the method foo is that it implements the algorithm for a binary search. The value c functions as the midpoint for the algorithm. This requires that the list be in order. The values a and b are used to control the loop so as to let you search the correct portions of the list. If the value in the middle of the list is not equal to what you are looking for (i.e. x), then it looks either "above" or "below" in the list (since it is presumed to be in order). This is what is happening when either a or b is changed.
So, this searches for the value and returns the index number for that value if it is found. Otherwise, it returns -1. Since the value 41 is in the array, it returns 6.
If you do not recognize this algorithm, you are likely to have some problems—and will have to trace the code!!
What is the difference between inorder traversal of a binary search tree and a preorder traversal?
In order traversal processes the left subtree, then the root node, then the right subtree, whereas preorder processes the root node, left subtree, then right subtree.
In order traversal processes the left subtree, then the root node, then the right subtree, whereas preorder processes the root node, left subtree, then right subtree.
They are similar.
They are similar.
The only difference is that in order processes the root node, whereas preorder does not.
The only difference is that in order processes the root node, whereas preorder does not.
Preorder searches through the tree from lowest to highest, inorder does not.
Preorder searches through the tree from lowest to highest, inorder does not.
In order traversal processes the right subtree, then the root node, then the left subtree, whereas preorder processes the left subtree, then the root node, the the right subtree.
In order traversal processes the right subtree, then the root node, then the left subtree, whereas preorder processes the left subtree, then the root node, the the right subtree.
Explanation
In this case, the names help to identify the different types of traversals. In order traversal processes the binary tree "in order", meaning it will go through the left subtree, process the node, then go on to the right. Why is this in order? Because remember, a binary sort tree lists any value less than the node to the left, and any value greater to the right, so in order traversal will actually go from greatest to smallest.
Preorder traversal is the same except that it processes the root node first, hence the "pre" order.