►
From YouTube: 2019-10-18 Go Study Group
Description
Wrapping up binary search problem in Go
A
A
And
then
we're
also
gonna
pull
up
the
go
Prague's
repo,
so
the
linear
search
algorithm.
This
is
the
naive
part
of
working
up
to
a
binary
search
progression,
so
the
the
instinctive
and
or
the
knee-jerk
way
of
searching
through
a
list
for
an
item
you're
looking
for,
is
just
to
go
from
the
beginning
of
the
list
and
just
progress
through
it.
Until
you
find
the
thing
you're
looking
for.
A
We
have
this
function
here
and
we're
just
gonna
fill
in
the
details,
so
we're
gonna
be
provided
a
slice
of
sorted
integers
and
that's
really
important
for
the
binary
search,
but
not
so
much
for
the
linear
search,
and
then
we
have
a
needle.
The
thing
that
we're
looking
for
and
what
we're
gonna
do
is
we're
gonna
return,
the
index
of
where
that
needle
is
in
the
haystack
or
where
it
should
be.
If
we
want
to
insert
it
and
yeah
I
think
that's
it.
A
A
So
there's
two
there's
two
main
parts
to
this
test.
Let
me
blow
this
up
a
bit,
so
the
first
part
is
that
we
have
a
bunch
of
fixtures
for
the
haystacks,
the
needles
and
the
expected
indexes,
and
then
we
have
another
part
of
this
is
that
we
split
up.
We
were
reusing
parts
of
the
test
for
the
other
algorithms,
in
our
case,
we're
doing
a
sub
test
for
linear
search
and
then,
if
we
finish
that
we'll
get
to
a
sub
test
for
binary
search.
A
A
A
A
A
And
the
sub
test
that
we
want
is
linear,
search,
so
I
think
the
way
that
go
does
this
is
that
it
puts
like
an
underscore
for
spaces
in
the
sub
test.
Name,
I,
believe
that's
what
it
does.
Okay,
so
we've
got
an
issue
here
already.
It
doesn't
like.
Oh
because,
okay,
this
is.
Why
doesn't
like
that?
So
the
reason
why
is
I
was
using
the
wrong
function.
Print
F
is
a
format
to
formatted
print
where
it
expects
a
string
that
has
like
formatting
directives
inside
of
it.
A
A
A
There's
no
items
in
this.
Yes,
so
we
we
actually
passed
the
first
test
because
we
returned
negative
one
and
that's
what
they
want
here.
The
second
test
is
where
we
failed,
there's
only
one
value
in
here,
so
we
should
have
returned
index
zero.
So
to
get
this
to
pass,
we
what
we
need
to
do
is
actually
we
need
to
check.
You
know
if
needle
equals
actual
we're
gonna
return.
A
A
A
B
A
A
In
worst
case,
we're
gonna
have
if
we
have
n
items
in
the
list,
the
worst
case
is
going
to
be
Big,
O
n,
so
yeah,
that's
whenever
you
see
something
that
is
just
Big
O
and
that's
Q
key
for
linear
space
complexity,
I,
don't
think
we
used
any
extra
variables
here,
except
for
a
couple
little
variables
here
and
there,
which
are
it's
just
a
constant
number
here.
So
we
can
ignore
that
really
so
yeah
the
space
complexity
is
just
Big
O,
one
I,
think
I,
don't
think
yeah.
B
A
Yeah
it
doesn't
the
the
complete.
The
space
complexity
doesn't
increase
as
the
number
of
elements
increase,
we're
just
reusing
a
couple
variables
here
that
we've
declared
to
copy
the
values
of
the
current
element.
We're
in
so
that's
pretty
simple.
So
when
is
linear
search
appropriate,
like
I,
was
saying
earlier,
I've
written
a
lot
of
these
and
it's
cuz.
It's
simple.
It's
really
easy
to
write
a
linear
search,
you're,
just
ranging
over
a
list,
and
when
you
find
what
you
want,
you
exit
the
list.
A
So
the
big
thing
is
when
performance
doesn't
matter,
linear
search
is
really
nice
and
a
lot
of
times
at
least
I
think
the
work
that
we
do
here
get
lab
a
lot
of
times.
The
the
bottleneck
is
not
how
long
it
takes
you
to
traverse
over
a
simple
list
in
memory.
It's
usually
something
else
like
disk
or
network
or
something
to
that
effect.
If
you
have
a
small
list
of
things,
then
linear
search
is
good
enough.
A
lot
of
times.
B
A
That's
a
good
point:
I
think
the
the
big
rule
that
people
should
follow
is,
you
know,
add
complexity
after
you've
noticed
or
you
anticipate
a
performance
degradation
and
using
measuring
tools
is
a
good
way
to
do
that.
Understand
the
background
of
the
problem
when
you're
implementing
a
solution
is
important.
A
Another
thing
another
time,
I
think
that
linear
search
is
appropriate
is
when
the
solution,
when
you
know
that
the
thing
you're
looking
for
tends
to
be
at
the
beginning
of
the
list.
So
if
you've
got
some
kind
of
data
structure
that
is
moving
like,
let's
say
you
have
like
a
stack
or
something
or
some
kind
of
priority
queue,
yeah
some
type
of
data
structure
that
moves
the
most
commonly
accessed
data.
To
one
end,
then,
if
you
start
your
search
from
that
end,
chances
are
you're,
gonna
get
the
data
that
you're
looking
for.
A
There's
also
ways
that
you
can
enhance
linear
search.
So
one
of
the
things
that
I
found
while
researching
this
problem
is
that
there's
variations
of
linear
search
and
binary
search
where,
if
you
don't
find
what
you're
looking
for
on
the
first
one,
you
try
to
take
a
guess
and
like
jump
ahead
in
the
list,
a
certain
amount
and
then,
if
you
don't
find
it,
maybe
you
jump
more
and
then
once
you
do
pass
the
value
you're
looking
for.
Since
this
is
a
sorted
list,
then
you
can
back
track
and
you
can
do
something
like
that.
A
I
think
that
might
be
used
a
lot.
I,
don't
know
for
for
sure
as
a
fact,
but
I
think
that
might
be
used
a
lot
when
you're
dealing
with
like
rotational
discs
and
sequential
memory.
That
sort
of
thing,
if
you're,
if
you're
scanning
through
a
large
set-
and
you
want
to
find
something-
you
might
you
know,
ramp
up
your
your
linear,
search
and
spend
up,
because
you
know.
B
A
A
A
B
A
B
B
A
Yes,
some
of
this
stuff
I
think
you
know
we're
kind
of
analyzing
it
to
death,
but
this
is
like
really
intuitive
stuff
for
people
like
when
you're
naturally
dealing
looks
like
a
large
set
of
data.
You
want
to
kind
of
skip
ahead
and
like
find
these
markers
and
insert
things
into
a
specific
slot
right,
like
that's,
that's
kind
of
how
we
do
things
on
a
day
to
day
basis
we
kind
of
skip
ahead,
and
then
we
get
our
bearings
and
then
we
adjust
so
yeah.
This
is
cool.
I'm
gonna
read
this
yeah.
B
A
A
Now,
let's
move
on
to
the
prize
cow
here,
the
binary
search.
So
there's
two
ways
we
can
attack
this.
We
can
go
for
an
iterative
solution
or
we
can
go
for
a
recursive
solution.
I
think
we
should
go
for
the
iterative
solution.
First
cuz
that
one
it
makes
everything
obvious
and
then
once
we
make
everything
obvious,
then
we
can
kind
of
reduce
it
down
to
a
more
elegant
solution.
Recursively.
A
A
Just
to
recap,
on
what
binary
search
does
we're
gonna?
We
have
a
big
list
of
sorted
items.
We're
gonna
be
given
an
item
that
we're
looking
for
and
we're
gonna
keep
slicing
the
problem
set
in
half
to
find
that
solution.
So
first
we're
gonna
slice
in
half
in
the
middle.
We're
gonna
see
you
know,
is
this
middle
element?
A
A
A
A
A
A
For
some
reason,
why
am
I
it's
running
the
meta
baited
by
oh,
this
string,
so
the
way
to
go
does
test?
Is
it
just?
It
just
matches
this
string
here
with
this
string
here,
but
I
guess
it
doesn't
matter.
If
the
slash
is
there
because
it
still
is
running
meta,
binary
search.
That's
funny
didn't
realize
that.
A
So
we
can
just
ignore
this
for
right
now,
we're
focused
on
just
the
binary
search.
So
this
test
right
now
it
does
not
iterate
over
the
entire
list.
There's
no
a
for
loop
there.
It's
just
looking
at
the
first
element
and
if
the
first
element
it
works,
then
it
returns.
It
returns
the
solution.
Otherwise
it
just
says
I,
don't
know,
I,
don't
know
how
to
do
anything
else.
Here
you
go
negative
one.
A
A
So
the
problem
is,
we
need
to
save
our
place
throughout
this
loop.
We
need
that
to
be.
We
need
that
information
accessible
from
we
better
loop
iteration
to
loop
iterations,
so
that
we
can
progress
so
what
I'm
gonna
do
is,
instead
of
declaring
the
midpoint
or
instead
of
declaring,
where
we
are
in
the
list
at
the
inside
of
the
for
loop,
I'm
gonna
do
that
outside
the
loop.
If
that
makes
sense,
actually
we
don't
define
it
at
all
right
now.
So
what
is
that
there
is
a
implicit
set
of
arguments
here
that
we're
working
on?
A
A
Here
we
just
check
if
it's
equal,
but
we
need
we
if
it's
not
equal
the
best.
The
best
case
is
that
it's
equal
and
we're
done.
We
found
the
solution.
If
it's
not
equal,
then
that
means
that
we
need
to
check
if
it's
less
than
or
equal
to
or
greater
than
so
what
we
can
do
is
we
can,
instead
of
having
a
if
statement,
we
can
have
a
switch
statement.
Cuz.
We
have
three
cases
really.
We
have.
A
A
Will
come
to
back
to
that
so
now
we
see
that
we
need
to
define
these
points
and
then
another
thing
jumps
out
at
me.
We
have
this
midpoint
and
this
midpoint
right
now.
It's
gonna
be
the
same
thing
over
and
over
again
every
loop
of
this
every
iteration
of
this
for
loop.
This
midpoint
will
always
be
the
length
of
the
whole
slice
and
then
we're
gonna
divide
that
into
so.
We
want
this
midpoint
to
change
relative
to
the
start
and
end,
so
we
need
to
modify
that
oli.
A
B
A
So
our
second
case
in
the
test
is
actually
one
item
the
list,
so
we'll
get
to
see
that
so
the
other
thing
is
we
don't
what
we're
gonna
end
up
with
a
forever
loop,
because
we
don't
exit
on
these
other
cases
here,
we're
just
continuing
change.
So
what
we
need
to
do
is
we
need
to
update
start
and
end
so
that,
based
on
where
we
want
to
go
left
or
right,
we
update
the
section
of
the
slice
that
we're
dealing
with.
A
So
if
needle
is
less
than
the
midpoint,
the
thing
that
we're
looking
for
is
less
than
the
middle
point
we've
chosen.
Then
that
means
we
need
to
go
left
so
I'm
gonna
put
go
left
here
and
then
in
this
case
we
are
gonna,
go
right.
So
if
we're
going
left,
what
does
that
mean
that
the
new
start
and
end
are.
A
We
don't
want
to
reassign.
We
want
to
use
the
same
variables
that
we
declared
outside
the
for
loop,
so
we
don't
want
to
shadow
these.
In
other
words,
okay,
cool.
The
only
thing
missing
here
is
some
logging
to
get
an
idea
of
what's
going
on
so
what
I'm
gonna
do
in
the
for
loop
is
I'm
going
to
log
and
I'm
going
to
put
a
really
cool
emoji.
A
A
A
The
only
problem
is
sometimes
in
a
terminal.
The
the
emojis
they'll
be
variable,
width
and
sometimes
they'll.
Take
they'll
cover,
they'll
obstruct
a
character,
that's
right!
Next
to
it,
so
I
always
put
a
space
after
the
emoji
so
that
if
it
does
instruct
something
it
just
obstructs
the
space
okay
and
then
what
we
want
to
do
is
we
want
to
see
the
start
and
then
the
end.
A
A
So
it
was
searching
for
needle
3
and
haystack
1
3,
that's
the
one
that
failed
and
it
originally
started
off
with
1
0,
and
then
it
went
to
1
1
and
then
it
did
1
1
again
and
then
it
did
start.
0
1,
oh
also
I'm,
but
we
might
be
looking
at
multiple
different
cases
here,
because
we're
not
using
a
sub
test
for
every
single
search.
A
So
another
thing
I'm
going
to
do
is
I'm
gonna
put
in
sub
tests.
We
talked
about
this
last
week.
The
there
was
a
lot
of
desire
from
people
to
have
sub
tests
so
that
we
could
figure
out.
Where
is
stuff,
failing
because
it's
hard
to
look
through
the
logs
to
find
things
so
I'm
going
to
I'm
going
to
open
up
the
test
file
and
what
I'm
gonna
do
is
when
we
run
this
I'm
gonna
run
a
sub
test
for
each
one
of
the
haystacks
that
we
have
here.
B
B
A
A
So
originally
we
just
had
the
name
as
the
test
and
now
we're
gonna
have
the
name
of
the
test
divided
by
the
haystack
and
then
R,
the
needle
I.
Don't
know
how
that's
gonna
actually
print
but
we'll
see
down
here.
This
is
how
it
prints.
It
has
the
haystack
and
then,
and
then
the
needle,
and
what
we'll
do
just
to
clean
it
up
a
bit
is
we
will
get
rid
of
the
space
here.
These
spaces
are
just
creating
underscores,
so
they're
not
really
needed.
A
There
we
go
that's
a
little
cleaner,
okay
cool,
so
now
we
can
see
we
passed
the
first
three
tests
and
then
we
failed
when
we
tried
to
find
this
case.
So
in
this
case,
so
this
is
kind
of
interesting,
because
the
first
case
we
had
two
elements
in
list
and
we're
looking
for
the
first
element.
In
this
case
we
had
the
same
list
of
items
but
we're
looking
for
the
second
element,
so
the
the
function,
the
the
solution
is
failing
for
when
we
need
to
go
right.
A
A
A
A
Now
we
can
actually
see
the
logs
a
bit
better.
Oh
maybe
I
missed
something.
But
oh,
we
were
looking
at
the
the
test
summary
earlier,
so
that
was
my
bad.
We,
the
test
summary,
doesn't
have
the
logging,
but
we
can
still
see
that
the
individual
cases
passed
or
failed
over
here.
Oh
no,
it
doesn't
tell
us
that
it
passes
or
fails
when
we're
looking
at
the
logs.
So
we
still
have
to
go
look
down
below
for
that.
This
is
the
case
that
failed.
A
We
had
one
three
in
the
set
the
haystack
and
then
we
were
looking
for
needle
three
and
it
just
got
stuck.
It
was
looking
for
start,
one
end,
one
in
mid
zero
and
then
it
was
it
looks
like
it
went
right
and
when
it
went
right.
So
this
is
what
I
think
the
problem
is
on
line
37
here
we
assign
mid
to
start,
but
the
problem
is
we're.
Dividing
the.
A
We're
dividing
the
difference
of
start
and
end
and
we're
ending
up
with
end
is
one
start
as
zero
right,
because
it's
a
two-element
list
1/2
ends
up
being
zero.
When
you
have
an
integer
and
you
don't
have
a
it's
gonna,
it's
gonna
truncate
downwards
right.
It's
gonna!
It's
going
to
round
down
with
an
integer
when
you
divide
one
by
two.
So
that's
that's
the
problem
is
that
we're
losing
precision
here,
so
what
we
could
do
is
we
could
try
a
hacky
thing
and
we
can
just
put
plus
one
see
what
happens
there.
A
A
We're
getting
some
other
problems
in
places
where
we
go
left
so
yeah
I
think
we
should
try
to
modify
this
so
when
we
want
to
go
to
the
left.
I'm
gonna
exclude
the
mid,
because
I
think
that
once
we've
determined
that
the
mid
is
not
what
we're
looking
for,
we
can
get
rid
of
it.
So
I'm
gonna
try
this
and
then
I'm
gonna
try
this.
Let's
see
what
that
does
and
dealing
with
these
indexes
is
not
fun.
This
is
like
the
annoying
part,
yeah
the
most
annoying
problems,
so
that
still
doesn't
fix
it.
A
B
A
A
We're
ended
up
with
these
negative
values
and
I
believe
what's
happening.
Is
that
we're
we're
ending
up
with
an
end
minus
start
that
results
in
a
negative
value?
So,
if
end,
let's
go
look
at
the
what's
happening
in
that
failing
case,
so
that
failing
case
is
135
needle
five.
So
if
we
go
to
135
needle
files,
I.
B
A
In
this
case,
there's
only
three
elements
in
the
list,
so
it
should
take
at
most
two
iterations
to
find
the
solution,
because
what
it's
going
to
do
is
it's
going
to
check
value
three
right
and
then,
if
three
is
less
or
if
three
is
not
the
value
you're
looking
for
you
go
right,
whoops
what
happened
there.
So
when
we
see
start
one
two
mid
one,
here's
the
problem
so
start
is
one
and
mid
is
one.
If
you
go
right
and
you
start
to
mid
nothing
changes,
it's
the
same
value
again,
that's
the
problem.
A
Why
aren't
the
same
value
start
as
one
end
as
one?
Oh,
this
is
why
cuz
it's
the
length
of
haystack?
Oh,
this
is
a
this
is
an
error
on
my
part,
I
put
the
value
at
zero.
That's
why
you
see
this
yeah.
This
is
this
is
why
that
was
a
goof
I'm,
crazy,
trying
to
figure
out
why
this
wasn't
working.
That's
what
happens
in
a
live
coding.
Exercise!
Everything
that
can
go
wrong
will
go
wrong.
You
make
the
dumbest
mistakes
possible.
A
Okay,
so
that's
why
we're
running
into
problems
so
I
think
a
lot
of
stuff
we
added
in
here.
We
can
get
rid
of
all
this
hacky
stuff
that
I
thought
would
fix
the
problem,
but
it
probably
wasn't:
let's
see
what
happens
here
now
and
just
for
consistency.
I'm
gonna
go
back
to
what
we
had
before,
which
is
just
end
equals
med
star
equals
mid.
Let's
see
what
happens
now,.
B
Let's,
like
it
shrunk,
the
area
solicited
was
looking
in
because
you
can
see.
That
start
is
one
and
this
one
so
you're
now
looking
at
this
see
one
element
but
said
like
so,
the
success
case
is
needle
equals.
He's
back
at
MIT
and
MIT
is
always
0.
For
some
reason
we
did.
You
have
to
pick
that
make
should
be
1
and
start
is
1
again.
This
one
yeah.
A
A
A
A
B
A
If
we
put
start
here,
which
is
guaranteed
to
be
a
positive
value,
when
we're
going
or
it's
always
gonna
be
a
nonzero
number
when
we're
going
right,
then
that
keeps
us
within
the
range
we
have
to
keep
that
mid
point
within
the
range
so
yeah
that
was,
that
was
the
little
little
bugger.
So
now
we
have
a
solution
that
is
iterative,
but
how
would
we
do
this
recursively
and
how
would
we
do
it
recursively
in
only
a
few
minutes.
A
So
we'll
look
that
up
when
we
get
back
to
it,
so
just
to
wrap
things
up
the
what
we
have
to
do
is
we
have
to
basically
provide
all
these
parameters
the
start
and
end,
but
instead
of
going
into
a
for
loop,
we're
going
to
be
making
calls
to
a
secondary
front
or
the
same
function
over
and
over
again
I,
don't
know
it.
Can
it
be
the
same
one?
No,
it
has
to
be
a
new
function,
signature,
but
yeah
I
think
that's
all
we
have
time
for
to
do
this.
A
A
A
This
is
technically
supposed
to
be
an
easy
like
algorithm
to
do,
but
all
these
little
index
things
they
just
like
take
a
ton
of
time
right,
you're
like
why
isn't
this
index
correct?
Why
isn't
that?
Why
isn't
this
division
I
have
to
remember?
Oh
you
know
if
you
divide
this,
it's
gonna
truncate
the
value
or
you
know
if
you
move
it
to
this
side
and
this
index,
it's
like
all
this,
like
index,
math
that
you
have
to
do
to
keep
everything
organized
but
get
better
at
it
with
practice.
A
Okay,
there
we
go
so
I'm,
gonna
upload
these
solutions
and
I'll
upload
those
upload
this
video
and
next
week
we
will.
We
will
finish
binary
search
and
I
will
be
trying
to
figure
out
a
good
problem
from
this
concurrency
and
go
book
and
we'll
do
something
that
uses
channels
and
sync
primitives
and
we'll
try
to
simulate
some
work.
Maybe
we'll
try
to
mix
in
a
computer
science.
Fundamental
algorithm
that
we
can
do
is
like
a
distributed
work
kind
of
problem,
but
I.
B
Have
an
interesting
one
for
that.
It
come
up
with
the
solution,
but
there
is
a
concurrency
problem
called
the
dining
philosophers
problem,
which
is
very
like
there's,
like
seven
people
sitting
at
a
table
and
then
there's
like
one
fork
to
the
right
of
every
person.
But
there
is
like
only
six
forth,
so
you
know,
like
figure
out
how
to
synchronize
like
who
picks
up
the
fork
and
one.
A
Yeah,
we
can
definitely
do
that.
I
just
saw
an
implementation
of
that
on
leak
code,
so
I
know
there's
some
test-driven
ways
to
to
play
with
that.
So
I'm
gonna
take
a
look
at
that
and
maybe
that'll
be
a
good
introductory
problem
to
get
in
a
concurrency,
and
then
we
can
figure
out
something
a
little
comp
more
complicated
down
the
road
I'm.
B
A
The
big
thing
is,
we
need
to
come
up
with
the
success
criteria
and
then
we
need
to
use
the
go
race
detector,
so
the
goal
based
detector
well.
Another
thing
is:
if
we
end
up
with
a
deadlock,
because
I
think
what
the
dining
philosophers
problem
does
is.
It
introduces
like
deadlocks
right
where,
like
they
can
yeah
good
work.
So
if
we
end
up
with
a
deadlock,
the
go
runtime
will
I.
Think
I
think
the
go.
Runtime
will
just
kind
of
crash.
If
there's
a
deadlock,
it'll
detect
that.
A
It
knows
that
you're
doing
something
you're
not
supposed
to
do,
but
the
problem
with
the
race
detector
is
that
sometimes
it
doesn't
detect
the
race
if
the
conditions
during
runtime
aren't
present
like
you
might
only
detect
a
race
time,
some
of
the
time,
depending
on
how
you
wrote
your
code,
so
that
can
be
an
issue,
but
if
I
have
a
this
is
a
really
easy
way
to
do
it.
If
I
make
a
channel
and
then
I
just
try
to
read
from
that
channel.
A
This
should
deadlock,
because
there's
no
one
writing
to
this
channel
channels
are
supposed
to
be
between
two
different
they're
supposed
to
be
between
two
different
go
routines.
This
is
only
one
go
routine
here.
It's
just
the
go
routine
that
I'm
writing
in
right.
Now
the
the
test
deadlock
go
routine.
So
if
I
try
to
run
this.
B
A
A
Definitely
tell
you
and
I
believe
if
you
have
a
without
the
race
detector,
if
you
just
like
compiled
an
executable
in
the
go
runtime,
if
all
of
your
threads
are
asleep
I,
think
it
tells
you
that
so
we'll
have
to
take
a
look
at
that
a
bit
more
I'll
put
a
note
here.
What
happens
in
go
when
you
have
a
deadlock,
and
then
we
both
want
to
know
during
tests
with
the
race
detector
and
at
runtime
in
an
executable
and
yeah.
A
B
A
There
is
especially
with
go
with
the
go
routines.
There's
a
lot
of
fun
things
that
you
can
do
with
it,
and
a
lot
of
cool
sink
primitives
and
go.
We
can
definitely
explore
those
individually
and
see
you
know
how
to
use
them
cool,
well,
I'm,
going
to
call
it
here
we're
a
bit
over
thanks
Ellie
for
joining
next
week.
We
will,
we
will
definitely
wrap
up
binary
search
and
then
we'll
do
well
start
the
dining
philosophers
problem
all
right
have
a
good
weekend.
Thankful.