Design a binary search based algorithm

Assignment Help Data Structure & Algorithms

Reference no: EM132094104

Please answer all parts of the following in a detailed and easy to read manner.

Original array: 2, 3, 5, 8, 9, 10, 14, 18, 28, 30

Sorted, but rotated array: 8, 9, 10, 14, 18, 28, 30, 2, 3, 5

All the elements (except an element called the pivot at index p) of the sorted, but rotated array of integers have a property that they are less than the element fo the right of them.

Only the pivot element is greater than the element to the right of it.

In the above sorted, but rotated array of integers, the pivot is the integer 30 at index 66. Incidentally, the pivot also happens to be the largest element in the array and is the lasat element in the original sorted array (before the rotation).

In the above example, the pivot element 30 is the largest element of the array and is also the last element of the original sorted array (before the rotation).

a) Design a binary search based algorithm to identify the pivot in a sorted, but rotated array of integers

b) Extend the algorithm of (a) to do a successful search for a key that is present in the sorted, but rotated array.

c) Extend the algorithm of (a) to do an unsuccessful search for a key that is not present in the sorted, but rotated array.

d) For each of the algorithms in (a), (b), and (c), illustrate the execution of the algorithm for the array given in the problem statement.

e) Analyze the time complexity of the algorithms of (a), (b), and (c).

Note: In addition to describing the working of your algorithms, you should write the pseudo code for your algorithms of (a), (b), and (c)

Reference no: EM132094104

Questions Cloud

How would you represent this query as map : How would you represent this query as map() and reduce() functions in MapReduce where dog is the table?:

Watch the video and answer the following questions : Please watch the video and answer the following questions below.

What guidelines are needed when life safety is not concern : Life safety must be of paramount concern in almost all settings (except perhaps a few national security areas).

Efficiency of the production operation : Efficiency of the Production Operation Research the process of producing an expensive product (assume that it is something that must cost at least $1,000).

Design a binary search based algorithm : All the elements (except an element called the pivot at index p) of the sorted, but rotated array of integers have a property that they are less.

Write a two-paragraph submission about the lecture : Film critic Robert Horton's was on campus for a lecture a couple of years ago, and that lecture is available on YouTube.

What it takes to enter new markets : You are in a meeting to try to understand what it takes to enter new markets. What lessons can be learned from Walmart's experience in Mexico

Discuss how the definition of privacy that is commonly used : Discuss how the definition of privacy that is commonly used (freedom from observation) may differ from the definition of privacy.

Identify the problems on various carnival cruise lines : 1. Identify the problems on various Carnival Cruise Lines as included in the article. 2. What is the root cause of the problems?

User Account

All Pages