To find a local minimum in a field

Click For Summary
SUMMARY

The discussion focuses on finding a local minimum in a field of N integers, where A[0] and A[N+1] are defined as infinity. A local minimum A[I] satisfies the condition A[I-1] >= A[I] <= A[I+1]. The initial algorithm presented requires O(n) time complexity, which is insufficient for the goal of achieving better asymptotic performance. A proposed improvement involves using binary search techniques to efficiently locate the local minimum by leveraging the properties of the field.

PREREQUISITES
  • Understanding of local minima in arrays
  • Familiarity with binary search algorithms
  • Knowledge of time complexity analysis
  • Basic programming skills, particularly in Pascal
NEXT STEPS
  • Research binary search optimization techniques for finding local minima
  • Explore algorithms with O(log n) time complexity for array search
  • Study the implications of monotonicity in search algorithms
  • Implement and test the proposed binary search approach in Pascal
USEFUL FOR

Computer scientists, algorithm developers, and programmers interested in optimizing search algorithms for local minima in arrays.

alejandrito
Messages
7
Reaction score
0
Let A be a field of N integers and A[0] = A[N+1] = infinity. Element A is called a local minimum if A[I-1] >= A <= A[I+1]. Find an alogrithm that will find some local minimum in a time asymptotically better then O(n). Hint: Consider that in each field deffined as before there must exist at least one local minimum.
The best algorithm (or programme in Pascal) I´ve found is the following:
...
while (A[I+1] > A[I+2] and I<N-1) do I:=I+1;
LOCMIN:=A[I+1];
...
which needs maximally N-1 steps to find a local minimum, but this is not enough if we want the asymptotical difficulty better then O(n). Could anybody help me with improving the algorithm? Thanks.
 
Physics news on Phys.org
Do we know the field is monotonic approaching the minimum from both directions, with only one minimum? If so, then use a binary search to bounce back and forth across the minimum and home in on it. Maybe even estimate how far away the minimum is by the slop of a couple of samples, and jump to the expecte location and do the same slope calculation and jump again...
 
The field shouldn´t be monotonic necessarilly, but it seems that any using of binary search could reduce sufficiently the number of steps. I will have a look on your hints, thanks.
 

Similar threads

Finding a Local Minimum in a Complete Binary Tree with Log(N) Probes
  • · Replies 1 ·
Replies
1
Views
2K
Algorithm to find the minimum spanning tree on a planar graph
  • · Replies 1 ·
Replies
1
Views
2K
To find a local minimum in a field
  • · Replies 2 ·
Replies
2
Views
5K
Challenge: Find the minimum amount of draws possible for a list of integers
  • · Replies 9 ·
Replies
9
Views
3K
MHB Find path to minimum cost from start to finish
  • · Replies 19 ·
Replies
19
Views
2K
Python Finding a local max/min of a function in Python
  • · Replies 7 ·
Replies
7
Views
6K
MHB Minimum Degree of a Random Graph (Probabilistic Method)
  • · Replies 1 ·
Replies
1
Views
2K
MHB Finding a Local Minimum of $G$: Algorithm & Analysis
  • · Replies 22 ·
Replies
22
Views
5K
Solving the a7 + b7 = c7 + d7 Equation Using Heap Algorithm
  • · Replies 14 ·
Replies
14
Views
2K
Graduate Find global minimum of f(x1,x2, xn), with many local minima
  • · Replies 1 ·
Replies
1
Views
2K