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?
Question 1 a) Determine whether the language {a n b m c n | n >...
Question 1 a) Determine whether the language {a n b m c n | n > 0} is regular or not using pumping Lemma. b) Prove that the language {(ai bn | i, n > 0, i = n or i = 2n} is not regular using the Pumping Lemma.
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 to design and implement a JAVASCRIPT program that will allow us to determine the...
I need to design and implement a JAVASCRIPT program that will allow us to determine the length of time needed to pay off a credit card balance, as well as the total interest paid. The program must implement the following functions: displayWelcome This function should display the welcome message to the user explaining what the program does. calculateMinimumPayment This function calculates the minimum payment. It should take balance and minimum payment rate as arguments and return the minimum payment. So...
Foundation of Computer Science Describe an algorithm that takes as input a list of n integers...
Foundation of Computer Science Describe an algorithm that takes as input a list of n integers and produces as output the largest difference obtained by subtracting an integer in the list from the one following it. Write its corresponding program using your favorite programming language
hi i need answer for 4.1 4E database systems the complete book
hi i need answer for 4.1 4E database systems the complete book
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
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 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
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT