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

brianokken
PragProg Customers

Python Testing with pytest: pytest now requires markers to be declared (downloadable code)
Many tasks_proj/tests directories exist in chapters 2, 3, 5 that have tests that use the custom markers smoke and get, which are not decl...
#errata/book-python-testing-with-pytest
2 1383 2
New
jamis
PragProg Customers

The Ray Tracer Challenge: various errata
The following is cross-posted from the original Ray Tracer Challenge forum, from a post by garfieldnate. I’m cross-posting it so that the...
#errata/book-the-ray-tracer-challenge
4 2434 3
New
raul
PragProg Customers

Distributed Services with Go: Chapter 3 suggestions
Page 28: It implements io.ReaderAt on the store type. Sorry if it’s a dumb question but was the io.ReaderAt supposed to be io.ReadAt? ...
#errata/book-distributed-services-with-go
0 1302 3
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
gilesdotcodes
PragProg Customers

Modern CSS with Tailwind: setting up Rails app
In case this helps anyone, I’ve had issues setting up the rails source code. Here were the solutions: In Gemfile, change gem 'rails' t...
#errata/book-modern-css-with-tailwind
3 1278 2
New
swlaschin
PragProg Customers

Domain Modeling Made Functional: Missing diagram on page 18
The book has the same “Problem space/Solution space” diagram on page 18 as is on page 17. The correct Problem/Solution space diagrams ar...
#errata/book-domain-modeling-made-functional
1 1078 1
New
brian-m-ops
PragProg Customers

Python Testing with pytest, Second Edition: cards pip install error (page 12)
#book-python-testing-with-pytest-second-edition Hi. Thanks for writing the book. I am just learning so this might just of been an issue ...
#errata/book-python-testing-with-pytest-second-edition
4 1191 3
New
hgkjshegfskef
PragProg Customers

The Ray Tracer Challenge: cannot pass scaling test (page 69-70)
The test is as follows: Scenario: Intersecting a scaled sphere with a ray Given r ← ray(point(0, 0, -5), vector(0, 0, 1)) And s ← sphere...
#question/book-the-ray-tracer-challenge
1 1093 4
New
jwandekoken
PragProg Customers

Programming Phoenix LiveView: Live Upload Match Error
Book: Programming Phoenix LiveView, page 142 (157/378), file lib/pento_web/live/product_live/form_component.ex, in the function below: d...
#errata/book-programming-phoenix-liveview
7 1158 10
New
redconfetti
PragProg Customers

Docker for Rails Developers - 'docker-machine' command deprecated (page 156)
Docker-Machine became part of the Docker Toolbox, which was deprecated in 2020, long after Docker Desktop supported Docker Engine nativel...
/book-docker-for-rails-developers#suggestion
0 896 0
New

Other popular topics Top

PragmaticBookshelf
Backend>Learning Resources

Web Development with Clojure, Third Edition
Stop developing web apps with yesterday’s tools. Today, developers are increasingly adopting Clojure as a web-development platform. See f...
pragprog.com
#pragprog#web-development/clojure#published-book/book-web-development-with-clojure-third-edition
5 4584 1
New
PragmaticBookshelf
General Dev>Learning Resources

The Pragmatic Programmer, 20th Anniversary Edition
Andy and Dave wrote this influential, classic book to help their clients create better software and rediscover the joy of coding. Almost ...
pragprog.com
#pragprog#published-book/book-the-pragmatic-programmer-20th-anniversary-edition
4 4782 0
New
Exadra37
General Dev>Hardware

What monitor(s) do you have for programming?
Please tell us what is your preferred monitor setup for programming(not gaming) and why you have chosen it. Does your monitor have eye p...
#monitors#coding#programming#development
227 11362 88
New
AstonJ
Backend>Questions

Erlang's not installing on macOS Big Sur "You are natively building Erlang/OTP for a later version of MacOSX than current version"
Just done a fresh install of macOS Big Sur and on installing Erlang I am getting: asdf install erlang 23.1.2 Configure failed. checking ...
#macos/erlang#big-sur#asdf
10 6212 8
New
AstonJ
General Dev>Hardware

Planck vs Preonic vs Subatomic (Keyboards)
I ended up cancelling my Moonlander order as I think it’s just going to be a bit too bulky for me. I think the Planck and the Preonic (o...
/keyboards#mechanical-keyboards#ortholinear#planck#preonic
105 17596 47
New
DevotionGeo
General Dev>Dev Chat

The V Programming Language
The V Programming Language Simple language for building maintainable programs V is already mentioned couple of times in the forum, but I...
#programminguages/v
21 13874 7
New
DevotionGeo
General Dev>Questions

Do you prefer regular mechanical keyboards or low profile mechanical keyboards and why?
I have always used antique keyboards like Cherry MX 1800 or Cherry MX 8100 and almost always have modified the switches in some way, like...
/keyboards#mechanical-keyboards
27 3877 9
New
PragmaticBookshelf
Backend>Learning Resources

Engineering Elixir Applications
Develop, deploy, and debug BEAM applications using BEAMOps: a new paradigm that focuses on scalability, fault tolerance, and owning each ...
pragprog.com
#pragprog/elixir#published-book/book-engineering-elixir-applications
40 7136 21
New
PragmaticBookshelf
Backend>Learning Resources

Agile Web Development with Rails 8
Get the comprehensive, insider information you need for Rails 8 with the new edition of this award-winning classic. Sam Ruby @rubys ...
pragprog.com
#pragprog#web-development/ruby/rails#published-book/book-agile-web-development-with-rails-8
12 7404 7
New
PragmaticBookshelf
Backend>Learning Resources

MySQL 9 Essentials
A concise guide to MySQL 9 database administration, covering fundamental concepts, techniques, and best practices. Neil Smyth MySQL...
pragprog.com
#pragprog#published-book/mysql/book-mysql-9-essentials
2 4162 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