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

Language HTML and Javascript Here is a string: " Hi, my name is John. I am...
Language HTML and Javascript Here is a string: " Hi, my name is John. I am a student at Rutgers University. I am currently taking a Web Class." 1. Change "Rutgers University" to "RUTGERS UNIVERSITY" 2. Replace "Web Class" to "Web Client and Server side Programming"
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...
This is for Javascript programming language: A. Class and Constructor Creation Book Class Create a constructor...
This is for Javascript programming language: A. Class and Constructor Creation Book Class Create a constructor function or ES6 class for a Book object. The Book object should store the following data in attributes: title and author. Library Class Create a constructor function or ES6 class for a Library object that will be used with the Book class. The Library object should be able to internally keep an array of Book objects. B. Methods to add Library Class The class...
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...
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.
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
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...
home / study / engineering / computer science / questions and answers / i have a...
home / study / engineering / computer science / questions and answers / i have a c++ question, its already posted on here ... Question: I have a c++ question, its already posted on here ... Bookmark I have a c++ question, its already posted on here but the answer given is way too complex and i dont understand it... its only the first month of c++ so please use the basic code... thank you. Assume that ax^2 + bx...
I am unsure as to why I cannot solve my Computer Science question I was just...
I am unsure as to why I cannot solve my Computer Science question I was just wondering if someone could show me exactly what they would do the code is in C++: write a program that display the following manual for user to chose among calculations Please select one of the following: addition subtraction multiplication division exit The program will then read in the user entry. when the user chose "1", it will ask the user "Please enter two numbers...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT