Computers and Technology, 12.03.2020 17:44, bankskry

We know that binary search on a sorted array of size n takes O(logn) time. Design a similar divide-and-conquer algorithm for searching in a sorted singly linked list of size n. Describe the steps of your algorithm in plain English. Write a recurrence equation for the runtime complexity. Solve the equation by the master theorem

Answers: 2

Show answers

Answers

answered: andreal7915

Here, start node(set to Head of the list), and the last node(set to NULL initially) are given.

The middle is calculated using two pointers approach.

Traverse linked list using two pointers. Move one pointer by one and other pointer by two. When the fast pointer reaches end slow pointer will reach middle of the linked list.

If middle’s data matches the required value of search, return it.

Else if middle’s data < value, move to upper half(setting start to middle's next).

Else go to lower half(setting last to middle).

The condition to come out is, either element found or entire list is traversed. When entire list is traversed, last points to start i.e. last -> next == start.

See attached pictures.

Explanation:

See attached pictures for detailed explanation.

We know that binary search on a sorted array of size n takes O(logn) time. Design a similar divide-a

answered: Guest

Ibelieve its true but not sure hope this .

answered: Guest

a social news website is an internet website that features user-posted stories. such stories are ranked based on popularity, as voted on by other users of the site or by website administrators. users typically comment online on the news posts and these comments may also be ranked in popularity. since their emergence with the birth of web 2.0, social news sites have been used to link many types of information, including news, humor, support, and discussion. all such websites allow the users to submit content and each site differs in how the content is moderated. on the slashdot and fark websites, administrators decide which articles are selected for the front page. on reddit and digg, the articles that get the most votes from the community of users will make it to the front page. many social news websites also feature an online comment system, where users discuss the issues raised in an article. some of these sites have also applied their voting system to the comments, so that the most popular comments are displayed first. some social news websites also have a social networking function, in that users can set up a user profile and follow other users' online activity on the website.

Other questions on the subject: Computers and Technology

Computers and Technology, 23.06.2019 21:20, FlowerChild1229

For positive constants a and b, the force between two atoms in a molecule is given f(r) = −a r2 + b r3 , where r > 0 is the distance between the atoms. note: a and b are upper case letters. (a) find f '(r) = (b) find the critical point for f(r). r = (c) find f ''(r) = (d) find the value of r so that f ''(r) = 0.

Answers: 1

continue

Computers and Technology, 24.06.2019 00:00, Amrinderkhattra

Visualizing a game of “tag” to remember the meaning of contagious

Answers: 3

continue

Computers and Technology, 24.06.2019 12:10, breezer20042

What is it called during the editing process when the processor ensures that a character holding a coffee mug from one angle is holding the same mug in the same way when the shot switches to another camera at another angle? cinematography continuity technology prop use

Answers: 1

continue

Computers and Technology, 24.06.2019 15:00, MilanPatel

In excel, what happens to the cell contents when you click and drag a cell into multiple cells?

Answers: 1

continue

Do you know the correct answer?

We know that binary search on a sorted array of size n takes O(logn) time. Design a similar divide-a...