Baby loop, Parent loop

[hardworkingfortheone]

https://gist.github.com/codecademydev/0ddf4b63ae4a8c9f26912c432fa5245d

hello!

this is a binary search algorithm for a sapesely sorted dataset.

i’m stuck in line 7, “mid= (first+last)//2”

let me take an example where i’m on line 15 and the condition is met.
then ‘mid’ would be assigned to ‘right’(line 16)
and then it would break out of nested loop(line 17)
then it would go back to line 6 where parent loop begins.
And here the problem is. line 7

3 possible ways.

1. line 7 would override line 16
2. line 7 would be dismissed.
3. I am wrong about something.

i don’t think 1 is right . if it’s right,it would keep resetting mid to (first+last)//2 and turn into infinite loop

which one is right?

thanks!

[stetim94]

is this an exercise? If so, can you please share exercise url? I want to have a look at the instructions.

i would also like to see what the arguments could possible be. Your code feels complex for what it does, but i can’t be certain until i have seen the requirements.

i wrote my own implementation, only check it out if feel like it:

def sparse_search(data, search_val):
  print("Data: " + str(data))
  print("Search Value: " + str(search_val))
  left = 0
  right = len(data)-1
  mid = len(data) // 2
  while left <= mid or right >= mid:
    if data[left] == search_val:
        return "{0} found at position {1}".format(search_val, left)
    elif data[right] == search_val:
        return "{0} found at position {1}".format(search_val, right)
    
    left += 1
    right -= 1

  return "not found"

print(sparse_search('abcd', 'b'))

[hardworkingfortheone]

it’s a project in the course, “search algorithm in python”
this is the link

https://www.codecademy.com/courses/search-algorithms/projects/searchcademy

[stetim94]

my absolute favorite tool in this kind of situation:

http://www.pythontutor.com/visualize.html#mode=display

when you have a break here:

       elif right <= last and data[right]:
          mid = right
          break
        elif left >= first and data[left]:
          mid = left
          break

this will break the while True loop, but then the code continuing executing here:

    if data[mid] == search_val:
      print("{0} found at position {1}".format(search_val, mid))
      return
    elif search_val < data[mid]:
      last= mid-1
    elif search_val > data[mid]:
      first= mid+1

before going to the next iteration of the while first<=last: loop

[hardworkingfortheone]

thanks for your reply!

but i have more questions

within parent loop, while first<= last:(line6)
there are 4 if statements. (including elif)

“if not data[mid]”(line8)
and “if data[mid] == search_val”(line24)
and two more elif lines below(line 27, 29)

1. Is line8 independent condition from line 24, 27, 29?
2. so “if statement” creates new if block, like line24
   and if i want to incorporate new condition into the block
   then i have to use elif, not if. like line 27,29. is this right?

<in short, my question is like this>
[if] [if elif elif] [if elif] [if] [if elif] [if else] is this right???

[stetim94]

the visualization tool i provided allows you to step through your code, and see the values of each variable at each step, have you done so?

[hardworkingfortheone]

i didn’t what that was, but now i see!

such an amazing tool, thanks a lot
now i can understand better how it works!
thank you so much!

[stetim94]

The thing that is even better, is that you came to the insight yourself. I don’t think any explanation can beat that