(Java) Problem 12.4 - alternative solution?

#1

Hi,

I’d like to know if the following solution is valid for problem 12.2 - base case (distinct elements)

public static int find(List A){

int left = 0;
int right = A.size()-1;
while(left <= right){
int middle = left + (right - left) / 2;
if (middle >=1 && middle <= A.size() -2 ){
if (A.get(middle).compareTo(A.get(middle-1))<0&&A.get(middle).compareTo(A.get(middle+1))<0){
return middle;}
else if (A.get(middle).compareTo(A.get(0))>0){
left=middle+1;
} else { right=middle-1;}
}}
return -1;
}

Basically, if the middle element is the smallest element in the cyclically sorted list, this is it.
Otherwise, if the value of the middle element is bigger than the value of the starting index, we have to search to the right of the middle; if the value of the middle element is smaller than the value of the starting index, we have to search to the left of the middle.

0 Likes
#2

I think the idea looks good to me, and you might want to use our program to check with yours as that is the best way to verify it :stuck_out_tongue:

0 Likes
#3

I had to refine the solution a bit to handle some corner cases

0 Likes