CODEWITHSUNDEEP
algorithmbinary-search
Joji
Joji

Reputation: 5625

How to find the largest number in an array made by a ascendingly sorted array and a descendingly sorted array

for an array like [1, 2, 4, 6, 8, 7, 5], how do we efficiently find the largest number in it? We know that the first part of the array is 1, 2, 4, 6, which is ascendingly sorted and the second part is 8, 7, 5 which is a descendingly sorted array.

The simply solution would be iterate through the array, but given the array is made of two sorted array, I would image the search can be done by some sort of binary search variation to achieve o(logn) runtime complexity. However I cannot seem to come up with the solution.

Upvotes: 0

Views: 71

Answers (1)

Mitch
Mitch

Reputation: 3418

What you are asking for is equivalent to finding the "peak" of an array. Here is logarithmic time solution to the problem

Upvotes: 2

Related Questions