Author |
Topic: Finding one local minima. (Read 1773 times) |
|
bazinga
Junior Member
Gender: 
Posts: 53
|
 |
Finding one local minima.
« on: Mar 28th, 2011, 8:43am » |
 Quote  Modify
|
Suppose we are given an array A[1 .. n] with the special property that A[1] ≥ A[2] and
A[n − 1] ≤ A[n]. We say that an element A[x] is a local minimum if it is less than or equal
to both its neighbors, or more formally, if A[x − 1] ≥ A[x] and A[x] ≤ A[x + 1]. For example,
there are five local minima in the following array:
9 7 7 2 1 3 7 5 4 7 3 3 4 8 6 9
We can obviously find a local minimum in O(n) time by scanning through the array. Describe
and analyze an algorithm that finds a local minimum in O(log n) time
Source
QuestionNumber:11
Would this java code solve it correctly?
Code:
public int getOneLocalMinimum(int lowIndex, int highIndex) {
if (lowIndex > highIndex) {
return -1;
}
if (lowIndex == highIndex) {
return lowIndex;
}
if (lowIndex + 1 == highIndex) {
if (elements[lowIndex] < elements[highIndex]) {
return lowIndex;
}
return highIndex;
}
int midIndex = (lowIndex + highIndex) / 2;
if ((elements[midIndex] <= elements[midIndex - 1])
&& (elements[midIndex] <= elements[midIndex + 1])) {
return midIndex;
}
if (elements[midIndex] >= elements[midIndex + 1]) {
return getOneLocalMinimum(midIndex, highIndex);
} else {
return getOneLocalMinimum(lowIndex, midIndex);
}
|
|
|
|
 IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print