We have an assignment to search for the minimum element of a sorted array that is shifted to the right afterwards. For example: [1, 5, 6, 19, 56, 101] becomes [19, 56, 101, 1, 5, 6]. The method should be implemented using a divide and conquer algorithm and it should have a better asymptotic time complexity than O(n). EDIT: I forgot to add that the elements int the array are unique.
I already implemented a method and wanted to ask if this is better than O(n) and if there are ways to improve my method.
public class FindMinimum {
public void findMinimum(int[] arr) {
// the recursive method ends when the length of the array is smaller than 2
if (arr.length < 2) {
return;
}
int mid = arr.length / 2;
/*
* if the array length is greater or the same as two, check if the middle
* element is smaller as the element before that. And print the middle element
* if it's true.
*/
if (arr.length >= 2) {
if (arr[mid - 1] > arr[mid]) {
System.out.println("Minimum: " + arr[mid]);
return;
}
}
/*
* separate the array in two sub-arrays through the middle and start the method
* with those two arrays again.
*/
int[] leftArr = new int[mid];
int[] rightArr = new int[arr.length - mid];
for (int i = 0; i < mid; i++) {
leftArr[i] = arr[i];
}
for (int i = mid; i < arr.length; i++) {
rightArr[i - mid] = arr[i];
}
findMinimum(leftArr);
findMinimum(rightArr);
}
}
In Java you could use a List because than you can create a Sublist.
private Integer findMinimum(List<Integer> list) {
if (list.size() < 2)
return list.get(0);
int mid = list.size() / 2;
// create left and right list
List<Integer> leftList = list.subList(0, mid);
List<Integer> rightList = list.subList(mid, list.size());
if (leftList.get(leftList.size() - 1) <= rightList.get(rightList.size() - 1))
return findMin(leftList);
else
return findMin(rightList);
}
When you create a Sublist with Java there is no copy. So to create a new Sublist takes a complexity of O(1). So the function has a complexity of O(logn).