Implementing Array Algorithms
Help Questions
AP Computer Science A › Implementing Array Algorithms
Given the following array, find the index of the first occurrence of target using binary search on a sorted array that may contain duplicates. Input: sorted int[] a ($0 \le n \le 10^5$), int target. Output: smallest index i with ai==target, else -1. Example: a=1,2,2,2,5, target=2 -> 1. Which method is correct?
public static int firstIndex(int[] a,int target){
int lo=0, hi=a.length-1, ans=-1;
while(lo<=hi){
int mid=(lo+hi)/2;
if(a[mid]==target){ ans=mid; hi=mid-1; }
else if(a[mid]<target) lo=mid+1;
else hi=mid-1;
}
return ans;
}
public static int firstIndex(int[] a,int target){
int lo=0, hi=a.length-1;
while(lo<=hi){
int mid=(lo+hi)/2;
if(a[mid]==target) return mid;
if(a[mid]<target) lo=mid+1; else hi=mid-1;
}
return -1;
}
public static int firstIndex(int[] a,int target){
int lo=0, hi=a.length-1, ans=-1;
while(lo<=hi){
int mid=(lo+hi)/2;
if(a[mid]==target){ ans=mid; lo=mid+1; }
else if(a[mid]<target) lo=mid+1;
else hi=mid-1;
}
return ans;
}
public static int firstIndex(int[] a,int target){
int lo=0, hi=a.length;
int ans=-1;
while(lo<=hi){
int mid=(lo+hi)/2;
if(a[mid]>=target){ ans=mid; hi=mid-1; }
else lo=mid+1;
}
return (a[ans]==target)? ans : -1;
}
Explanation
This question tests AP Computer Science A skills: implementing array algorithms, specifically modified binary search for finding first occurrence in arrays with duplicates. When duplicates exist, standard binary search may find any occurrence, but finding the first requires continuing the search in the left half even after finding a match. In this problem, students must modify binary search to always find the leftmost occurrence of the target. Choice A is correct because when target is found, it saves the position in ans but continues searching left (hi=mid-1) to find earlier occurrences, ensuring the first index is returned. Choice B is incorrect because it returns immediately upon finding any occurrence, which may not be the first one in arrays with duplicates. To help students: Trace through examples with multiple duplicates to show why continuing left is necessary. Emphasize how binary search can be modified for different requirements.
Implement an algorithm to sort the following array in ascending order using insertion sort (no built-in sort): int[] a. Constraints: $0 \le n \le 10^4$. After sorting, a must be in nondecreasing order. Example: 4,1,3 -> 1,3,4. Which method correctly sorts the array?
public static void insertionSort(int[] a){
for(int i=1;i<a.length;i++){
int key=a[i];
int j=i-1;
while(j>0 && a[j]>key){
a[j+1]=a[j];
j--;
}
a[j]=key;
}
}
public static void insertionSort(int[] a){
for(int i=0;i<a.length;i++){
int min=i;
for(int j=i+1;j<a.length;j++) if(a[j]<a[min]) min=j;
int t=a[i]; a[i]=a[min]; a[min]=t;
}
}
public static void insertionSort(int[] a){
for(int i=1;i<=a.length;i++){
int key=a[i];
int j=i-1;
while(j>=0 && a[j]>key){ a[j+1]=a[j]; j--; }
a[j+1]=key;
}
}
public static void insertionSort(int[] a){
for(int i=1;i<a.length;i++){
int key=a[i];
int j=i-1;
while(j>=0 && a[j]>key){
a[j+1]=a[j];
j--;
}
a[j+1]=key;
}
}
Explanation
This question tests AP Computer Science A skills: implementing array algorithms, specifically the insertion sort algorithm. Insertion sort builds a sorted portion from left to right by inserting each element into its correct position among previously sorted elements. In this problem, students must implement insertion sort with correct loop bounds and element shifting logic. Choice A is correct because it starts from index 1, uses j>=0 to allow insertion at index 0, properly shifts elements right while searching for the insertion position, and inserts at j+1 after the loop. Choice B is incorrect because the while condition j>0 prevents insertion at index 0, causing incorrect sorting when the key should be the smallest element. To help students: Trace through the algorithm with small arrays, showing how the sorted portion grows. Emphasize the importance of boundary conditions in loops.
Given a sorted int[] ids (ascending, distinct) with $0 \le n \le 10^5$, write a method that returns the index of target using binary search, or -1 if not found. No built-in search. Example: ids=2,5,8,10, target=8 -> 2. Which implementation is correct?
public static int find(int[] ids,int target){
int lo=0, hi=ids.length-1;
while(lo<hi){
int mid=(lo+hi)/2;
if(ids[mid]==target) return mid;
if(ids[mid]<target) lo=mid; else hi=mid;
}
return -1;
}
public static int find(int[] ids,int target){
int lo=0, hi=ids.length;
while(lo<=hi){
int mid=(lo+hi)/2;
if(ids[mid]==target) return mid;
if(ids[mid]<target) lo=mid+1; else hi=mid-1;
}
return -1;
}
public static int find(int[] ids,int target){
for(int i=0;i<ids.length;i++) if(ids[i]==target) return i;
return -1;
}
public static int find(int[] ids,int target){
int lo=0, hi=ids.length-1;
while(lo<=hi){
int mid=(lo+hi)/2;
if(ids[mid]==target) return mid;
if(ids[mid]<target) lo=mid+1; else hi=mid-1;
}
return -1;
}
Explanation
This question tests AP Computer Science A skills: implementing array algorithms, specifically binary search on sorted arrays. Binary search is a divide-and-conquer algorithm that efficiently finds elements by repeatedly halving the search space. In this problem, students must implement binary search with correct boundary conditions and index calculations. Choice A is correct because it properly initializes hi to ids.length-1, uses the correct loop condition lo<=hi, and updates boundaries correctly (lo=mid+1 and hi=mid-1) to avoid infinite loops. Choice B is incorrect because it initializes hi to ids.length, which could cause an ArrayIndexOutOfBoundsException when accessing ids[mid]. To help students: Draw diagrams showing how lo, hi, and mid change during execution. Practice with arrays of different sizes, including edge cases like single-element arrays.
Simulate a line at a help desk using an array-based queue. Implement enqueue (add to back) and dequeue (remove from front) for up to $10^4$ operations. Use a circular buffer with int[] data and indices front, size (no java.util.Queue). Which code correctly dequeues one element and returns it, or returns -1 if empty?
public int dequeue(){
if(size==0) return -1;
int val=data[front];
size--;
return val;
}
public int dequeue(){
if(size==0) return -1;
int val=data[front];
front=front+1;
size--;
return val;
}
public int dequeue(){
if(size==0) return -1;
int val=data[front];
front=(front+1)%data.length;
size--;
return val;
}
public int dequeue(){
if(size==0) return -1;
front=(front+1)%data.length;
size--;
return data[front];
}
Explanation
This question tests AP Computer Science A skills: implementing array algorithms, specifically circular buffer queue operations. A circular buffer uses modulo arithmetic to wrap around array boundaries, efficiently utilizing fixed-size arrays for queue operations. In this problem, students must implement dequeue operation that removes and returns the front element while maintaining the circular buffer structure. Choice A is correct because it saves the value at front before updating, uses modulo arithmetic (front+1)%data.length to handle wraparound, and decrements size to maintain queue state. Choice C is incorrect because it updates front before saving the value, returning the wrong element (the one after the front). To help students: Visualize circular buffers with diagrams showing how front and rear pointers move. Practice tracing through enqueue and dequeue operations with small arrays.
Perform a 2D array operation: write a method that returns the transpose of an int[][] m with r rows and c columns ($1 \le r,c \le 200$). The result must be a new array with c rows and r columns where resultji = mij. Example: [1,2,3,4,5,6] -> [1,4,2,5,3,6]. Which code is correct?
public static int[][] transpose(int[][] m){
int r=m.length, c=m[0].length;
int[][] t=new int[c][r];
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
t[i][j]=m[j][i];
return t;
}
public static int[][] transpose(int[][] m){
int r=m.length, c=m[0].length;
int[][] t=new int[r][c];
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
t[j][i]=m[i][j];
return t;
}
public static int[][] transpose(int[][] m){
int r=m.length, c=m[0].length;
int[][] t=new int[c][r];
for(int i=0;i<=r;i++)
for(int j=0;j<c;j++)
t[j][i]=m[i][j];
return t;
}
public static int[][] transpose(int[][] m){
int r=m.length, c=m[0].length;
int[][] t=new int[c][r];
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
t[j][i]=m[i][j];
return t;
}
Explanation
This question tests AP Computer Science A skills: implementing array algorithms, focusing on 2D array manipulation and matrix operations. Matrix transpose swaps rows and columns, requiring careful attention to dimension changes and index mapping. In this problem, students must create a new array with swapped dimensions and correctly map elements from m[i][j] to t[j][i]. Choice A is correct because it creates the result array with dimensions [c][r] (swapped from original [r][c]) and correctly assigns t[j][i]=m[i][j] for all valid indices. Choice B is incorrect because it creates the result array with wrong dimensions [r][c] instead of [c][r], causing ArrayIndexOutOfBoundsException when accessing t[j][i] for j>=r. To help students: Use concrete examples with non-square matrices to highlight dimension changes. Draw the mapping between original and transposed positions.