Question

In: Computer Science

Hi, I found this in the book balanced introduction to computer science,Javascript language, ⌈Log2(N)⌉ determine the...

Hi,

I found this in the book balanced introduction to computer science,Javascript language, ⌈Log2(N)⌉ determine the number of checks it takes for binary search to find an item. I also saw this ⌈Log2(N)⌉+1 to find the number of checks,

what is the difference between these 2, which one should I use?

Solutions

Expert Solution

Binary search is a divide-and-conquer algorithm. To find an element in a sorted array, A , we first compare the search element with A[n2] , and recurse either on the first half, A[0,…,n2–1] , or on the second half, A[n2,…,n−1] .

Thus, we can find the recurrence to be T(n)=T(⌈n2⌉)+O(1) . The first part of the recurrence should be obvious. The O(1) part comes because we have to determine which half of the array to recurse on. This comparison can be done in constant time.

To solve this recurrence relation, we can either use the master theorem, or solve it algebraically. I’ll solve it algebraically, since the solution follows trivially from the master theorem with a=1,b=2,d=0 .

First, not that T(1)= 1 . Now, suppose that n=2k⟹k=⌈log2n⌉ . Thus, we have that

T(2k)=T(2k2)+1

=T(2k−1)+1

=[T(2k−2)+1]+1

=T(2k−2)+2

=[T(2k−3)+1]+3

=T(2k−k)+k

=T(20)+k

=T(1)+k

Now, since T(1)=1 , we have that T(2k)=1+k . Thus, T(n)=⌈log2n⌉+1 .

Therefore, performing binary search, you should expect to have ⌈log2n⌉+1 comparisons where n is the number of elements in your search space.


Related Solutions

Book - Introduction to Programming Using Visual Basic 11th Edition by David I. Schneider Programming Language...
Book - Introduction to Programming Using Visual Basic 11th Edition by David I. Schneider Programming Language - Visual Studio 2017 RESTAURANT MENU Write a program to place an order from the restaurant menu in Table 4.13. Use the form in Fig. 4.70, and write the program so that each group box is invisible and becomes visible only when its corresponding check box is checked. After the button is clicked, the cost of the meal should be calculated. (NOTE: The Checked...
In regards to the book "Philospohy of Science: A Very Short Introduction", chapter 2, what are...
In regards to the book "Philospohy of Science: A Very Short Introduction", chapter 2, what are your thoughts on hume's problems? Do you think it is a genuine problem that scientists should pay attention to?
Hi there, for this question. I found the answer in excel sheet to be negative. is...
Hi there, for this question. I found the answer in excel sheet to be negative. is ther something wrong with my calculation: Using the approach covered in your textbook calculate the geometric average annual rate of return over five years given the following annual rates, year 1 = 5.10%, year 2 = 4.95%, year 3 = 4.83%, year 4 = 4.75% and year 5 = 4.70% . What is the arithmetic average? Explain the difference. (Rates as a percentage accurate...
I need Introduction about (understanding computer fraud in accounting environment) the introduction should include: Orient the...
I need Introduction about (understanding computer fraud in accounting environment) the introduction should include: Orient the readers towards the topic Explain the importance and relevance of the topic Justifies the choice of the topic Provides a concise overview of relevant literature to make the proposal sound
I need an introduction to computer fraud and how it happens in the accounting environment
I need an introduction to computer fraud and how it happens in the accounting environment
In fall 2010, students in my 2 p.m. section of the Introduction to Biological Science I...
In fall 2010, students in my 2 p.m. section of the Introduction to Biological Science I class reported their height below on the first column of the table, while my 5 p.m. section reported their height on the second column. I wondered: are the average heights of these two sections significantly different? Students’ height in Introduction to Biological Science I courses (inches) 2 pm 5 pm 70 67 69 61 67 59 62 62 70 62 69 68 66 67...
i want to write research paper in the field of computer science but cant decide the...
i want to write research paper in the field of computer science but cant decide the topic for that plz help me.
hi please answer it by computer not a hand wtiting and by your own word I...
hi please answer it by computer not a hand wtiting and by your own word I have a project about psychological health , so I need a help to do this : Post communication strategies Post action and evaluation plans
Hi, I have a question. I am doing Preminary Analytical Procedure for Apollo Shoes. I found...
Hi, I have a question. I am doing Preminary Analytical Procedure for Apollo Shoes. I found unusual percentage for Line of Credit( increased to 344%) and Accounts Payable decreased by 59%. Is this cause RMM increase? I have hard time understanding this project. Please help me. Thanks.
This is my presentation/ research topic, Professionals conduct in Computer Science. I have to give a...
This is my presentation/ research topic, Professionals conduct in Computer Science. I have to give a 10 minutes presentation about it but I dont understand this topic and really dont know what to talk about to make it interesting for the class. I have to talk about what are the problems, questions, my assumption, point of view, and conclusion about the topic, which I am very confused. Im really scared of doing public speaking buy will try my best.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT