local-minima

The pseudo / java code find only global minima and… Himadri Sarkar - Mar 0, 2014The pseudo / java code find only global minima and that too when no other local minima exist. I don’t think this problem can be solved in less than O(n) Hi Himadri, thanks for the comment. But I think the code is intended to give us local minima, and as we are apply binary search logic, it is possible in O(log n). [Read More]

Problem: Given an array ‘a’ of N distinct integers, design an O(log N) algorithm to find a local minimum: an index i such that a[i-1] > a[i] < a[i+1]. Examples: a = [1,2,3,4,5] (increasing, increasing) a[0] is an LM a = [5,4,3,2,1] (decreasing, decreasing) a[n] is an LM a = [1,2,2,2,1] (increasing, decreasing) a[0] and a[n] are LMs Solution: **Brute force ** Go through each element 3 tuples, and compare them. [Read More]