PragProg Customers

A Common-Sense Guide to Data Structures and Algorithms, Second Edition: Ch. 2 Exercise 3

JoshuaWLindsay

JoshuaWLindsay

A Common-Sense Guide to Data Structures and Algorithms, Second Edition: Ch. 2 Exercise 3

@jaywengrow

“What is the maximum number of steps it would take to perform a binary search on an array of size 100,000?”

“To solve this, we need to count how many times we halve 100,000 until we get down to 1. If we keep dividing 100,000 by 2, we see that it takes us 16 times until we get down to about 1.53.
This means a worst-case scenario would take about 16 times.”

Maximum number of steps should be 17, not 16. Perhaps dividing by 2 should be performed until the result is less than 1.

Excerpt From
A Common-Sense Guide to Data Structures and Algorithms, Second Edition
Jay Wengrow
https://itunes.apple.com/WebObjects/MZStore.woa/wa/viewBook?id=0
This material may be protected by copyright.

1 comment
#errata/book-a-common-sense-guide-to-data-structures-and-algorithms-second-edition
1 507 1

First Post!

VipulSharma95

VipulSharma95

Yes, the answer should indeed be 17.

This is because log(base2) 100 is 16.61, which would be rounded up to 17.

Post #2

Where Next?

View thread on forum
View A Common Sense Guide To Data Structures And Algorithms Second Edition's book portal
Post errata for this book
Post a suggestion for this book
Post a question about this book
Post a review about this book
Home PragProg Customers
#errata/book-a-common-sense-guide-to-data-structures-and-algorithms-second-edition
1 507 1
Last post

Popular Pragmatic Bookshelf topics Top

duke_meister
PragProg Customers

The Ray Tracer Challenge - where are the errata?
As per the title, thanks.
/book-the-ray-tracer-challenge
6 1681 4
New
telemachus
PragProg Customers

Warnings in Python Testing With Pytest Chapter 2
Python Testing With Pytest - Chapter 2, warnings for “unregistered custom marks” While running the smoke tests in Chapter 2, I get these...
#pragprog#errata/book-python-testing-with-pytest
5 2081 1
New
HarryDeveloper
PragProg Customers

Programming Kotlin: Difference between SupervisorJob() and supervisorScope (324, 325)
Hi @venkats, It has been mentioned in the description of ‘Supervisory Job’ title that 2 things as mentioned below result in the same eff...
#question/book-programming-kotlin
0 2242 2
New
AleksandrKudashkin
PragProg Customers

Modern Front-End Development for Rails: B7 no main folder in the source code (page xv)
On the page xv there is an instruction to run bin/setup from the main folder. I downloaded the source code today (12/03/21) and can’t see...
#errata/book-modern-front-end-development-for-rails
2 1452 11
New
AndyDavis3416
PragProg Customers

Modern Front-End Development for Rails: ERROR in tsconfig.json Chapter_01/01
@noelrappin Running the webpack dev server, I receive the following warning: ERROR in tsconfig.json TS18003: No inputs were found in c...
/book-modern-front-end-development-for-rails
3 1438 3
New
jskubick
PragProg Customers

Kotlin and Android Development featuring Jetpack: Error in generated Game.java (page 136)
I’m under the impression that when the reader gets to page 136 (“View Data with the Database Inspector”), the code SHOULD be able to buil...
#question/book-kotlin-and-android-development-featuring-jetpack
2 1172 8
New
digitalbias
PragProg Customers

Build a Weather Station with Elixir and Nerves: Problem connecting to Postgres with Grafana
Title: Build a Weather Station with Elixir and Nerves: Problem connecting to Postgres with Grafana on (page 64) If you follow the defau...
#errata/book-build-a-weather-station-with-elixir-and-nerves
0 1962 4
New
creminology
PragProg Customers

Real Time Phoenix Errata P17: Getting first sample working with Phoenix 1.6.x
Skimming ahead, much of the following is explained in Chapter 3, but new readers (like me!) will hit a roadblock in Chapter 2 with their ...
#errata/book-real-time-phoenix
6 1116 5
New
davetron5000
PragProg Customers

Bug with dx/build - how to workaround until fix is up
Hello faithful readers! If you have tried to follow along in the book, you are asked to start up the dev environment via dx/build and ar...
#errata/book-ruby-on-rails-background-jobs-with-sidekiq
3 1178 19
New
bdarla
PragProg Customers

SQL Antipatterns, Volume 1: Volume 2?
Is there any plan for volume 2? :slight_smile:
#question/book-sql-antipatterns-volume-1
6 721 7
New

Other popular topics Top

Devtalk
General Dev>Dev Chat

What dev-related stuff have you been up to?
Reading something? Working on something? Planning something? Changing jobs even!? If you’re up for sharing, please let us know what you’...
#community
1063 23582 394
New
siddhant3030
General Dev>Dev Chat

Which vertical monitor do you use?
I’m thinking of buying a monitor that I can rotate to use as a vertical monitor? Also, I want to know if someone is using it for program...
#monitors#programming
51 4892 20
New
PragmaticBookshelf
Backend>Learning Resources

Programming WebRTC
Use WebRTC to build web applications that stream media and data in real time directly from one user to another, all in the browser. ...
pragprog.com
#pragprog#published-book/js#webrtc/book-programming-webrtc
27 6969 6
New
AstonJ
Science/Tech>Health & Diet

David Sinclair's new Lifespan podcast
We’ve talked about his book briefly here but it is quickly becoming obsolete - so he’s decided to create a series of 7 podcasts, the firs...
#health#podcasts#bio-hackers#david-sinclair
87 6790 49
New
PragmaticBookshelf
Backend>Learning Resources

Agile Web Development with Rails 7
Rails 7 completely redefines what it means to produce fantastic user experiences and provides a way to achieve all the benefits of single...
pragprog.com
#pragprog#web-development/ruby/rails#published-book/book-agile-web-development-with-rails-7
32 6600 9
New
PragmaticBookshelf
Backend>Learning Resources

Programming Ruby 3.2 (5th Edition)
Programming Ruby is the most complete book on Ruby, covering both the language itself and the standard library as well as commonly used t...
twitter.com
#pragprog/ruby/rails#published-book/book-programming-ruby-3-2-5th-edition
28 8550 13
New
PragmaticBookshelf
Community>In The Spotlight

Spotlight: Peter Ullrich (Author) Interview and AMA!
Author Spotlight: Peter Ullrich @PJUllrich Data is at the core of every business, but it is useless if nobody can access and analyze ...
/elixir/phoenix/book-building-table-views-with-phoenix-liveview
72 4765 21
New
PragmaticBookshelf
Community>In The Spotlight

Spotlight: Bruce Tate (Author) Interview and AMA!
Author Spotlight: Bruce Tate @redrapids Programming languages always emerge out of need, and if that’s not always true, they’re defin...
/elixir/ruby/phoenix/book-seven-more-languages-in-seven-weeks/book-seven-languages-in-seven-weeks#liveview/book-programming-phoenix-liveview
54 5678 23
New
AstonJ
Backend>Questions

Psql: error: connection to server on socket "/tmp/.s.PGSQL.5432" failed: No such file or directory
If you’re getting errors like this: psql: error: connection to server on socket “/tmp/.s.PGSQL.5432” failed: No such file or directory ...
#macos/rails/postgresql
1 5553 1
New
CommunityNews
Game Dev>In The News

Grand Theft Auto: Vice City | DOS games in browser
Open-source implementation of the classic GTA engine now running directly in your browser. Experience the reVC technology demo on DOS.Zon...
dos.zone
#games#browser
0 173 0
New
Back to top

Latest in A Common-Sense Guide to Data Structures and Algorithms, Second Edition

A Common-Sense Guide to Data Structures and Algorithms, Second Edition Portal ❯

PragProg Customers

Pragmatic Bookshelf PragProg Customers ❯

Latest on Devtalk

Devtalk ❯

We ❤️ helpful members!

We reward our most helpful members via our MOTM scheme - by giving away a whopping 25 books per year!

Member of the Month

Devtalk Sponsors

Pragmatic Bookshelf

Practical resources that improve the lives of professional developers.

Erlang Solutions

We build trusted fault-tolerant systems that scale to billions of users.

Honeybadger

Real-time error tracking, performance insights, and observability for devs.

EEF

Supporting innovation across the BEAM ecosystem.

coders51

We build reliable cloud platforms for business-critical systems.

Manning Publications

Develop your skills with books, videos, and courses.

AppSignal

Catch errors, track performance, monitor hosts and more.

WyeWorks

Enabling companies to succeed by building software people love.

Pragmatic Studio

Courses that move you from confusion to "Aha, now I get it!"

Linux New Media

Publishing Linux Magazine, ADMIN, and MakerSpace for 25+ years.

View all our sponsors ❯

Categories:

Sub Categories:

Popular Portals

Devtalk Sponsors

Pragmatic Bookshelf

Practical resources that improve the lives of professional developers.

Erlang Solutions

We build trusted fault-tolerant systems that scale to billions of users.

Honeybadger

Real-time error tracking, performance insights, and observability for devs.

EEF

Supporting innovation across the BEAM ecosystem.

coders51

We build reliable cloud platforms for business-critical systems.

Manning Publications

Develop your skills with books, videos, and courses.

AppSignal

Catch errors, track performance, monitor hosts and more.

WyeWorks

Enabling companies to succeed by building software people love.

Pragmatic Studio

Courses that move you from confusion to "Aha, now I get it!"

Linux New Media

Publishing Linux Magazine, ADMIN, and MakerSpace for 25+ years.

View all our sponsors ❯

We're in Beta

About us Mission Statement See our Roadmap