CS 371: Module 8: Exercise 0 (2 Points)

Developed by Professor Tralie and Professor Mongan.

---

Exercise Goals

The goals of this exercise are:

1. To implement data structures in python using object-oriented paradigms

Fill in the binary_search method to complete the binary search technique to find an element in a sorted array. Note that the // operator rounds the division down to the nearest int, which you'll need to do to keep them as indices. Refer to the image below to recall how this algorithm works:

Running into infinite loops is very common here! So if your code doesn't terminate quickly, you probably have an infinite loop, and you may need to refresh your page. Don't feel bad about this though...I had this happen to me when I implemented this for the first time in CS 174 last fall.

Enter your Ursinus netid before clicking run. This is not your ID number or your email. For example, my netid is ctralie (non Ursinus students can simply enter their name to get this to run, but they won't get an e-mail record or any form of credit)

Netid

Clicking Run below will check your work and, if it passes, will submit your work automatically. You must be connected to the VPN for submission to be successful! You will receive a copy of your code via e-mail, so you'll know that it was submitted if you receive that e-mail! VPN access requires Multi-Factor Authentication, which sends you a code when you log into the network. Instructions on configuring these for your account can be found here.

Student Code

def binary_search(arr, value): """ Parameters ---------- arr: list A *sorted* list of numbers value: float Number under search Returns ------- idx: int Index of the first occurrence of value in arr """ idx = -1 i1 = 0 i2 = len(arr)-1 mid = (i1+i2)//2 while i1 != i2: if arr[mid] < value: # TODO: Fill this in else: # TODO: Fill this in if arr[i1] == value: idx = i1 return idx

Test Code Block

arr = [9,9,12,14,19,19,20,21,25,29,36,37,39,44,46,47,47,49,58,64,64,65,67,67,69,70,72,77,79,80,81,82,83,87,87,88,88,88,88,99] for i in range(len(arr)): idx = binary_search(arr, arr[i]) print("{},{}".format(idx, arr[idx]), end=".")

Output

---