Starting from:
$17.99
Lab06: Binary Search
Lab06: Binary Search
1. Introduction In this exercise, we will complete one Python function in order to find a potential indexMatch i for a sorted list with distinct integers in which list[i] = i by using binary search.
2. Objectives The purpose of this assignment is to help you: • Practice binary search. • Refresh knowledge on python lists and functions. Note: Before you start, if you are not familiar with binary search, list or function in Python, you are recommended to review your lecture notes and the additional materials from Dr. Don Sheehy.
3. Background 3.1. Binary Search Binary search is a classic search algorithm which finds the position of a target value within a sorted list.1 In binary search, when we are looking for a particular item in a sorted list, we compare the targeted value with the median of the current list and break the list in half iteratively by keeping the half which may contain the targeted item. So, given a list of length !, the asymptotic running time of the binary search is !(!"#$). The following figure shows the implementation of a binary search for target value 7 on a list with length 17. With binary search, it takes only 4 steps to find target value, which is much faster than linear search asymptotically.
Fig2. 1 Visualization of Binary Search with Target Value Equal to 7
1 Cited from Wikipedia, Binary search algorithm. https://en.wikipedia.org/wiki/Binary_search_algorithm 2 Cited from Wikipedia. https://commons.wikimedia.org/wiki/File:Binary_Search_Depiction.svg#
2
4. Assignment In this assignment, we only need to complete indexMatch function in binary.py. The input of this function is a sorted list list1 with distinct integers. We need to utilize binary search to find out and return a potential index i for which list1[i] = i.
4.1. Index Match using Binary Search In order to have a nice understanding of the binary search implementation in index match, we give an example as the following.
For a certain input,
list1 = [-3, -1, 0, 2, 3, 4, 5, 6, 8, 12, 20]
we can visualize the item values and their corresponding indices as,
value -3 -1 0 2 3 4 5 6 8 12 20 index 0 1 2 3 4 5 6 7 8 9 10
where we can see 8 is the matched index that the indexMatch function should return.
Here, you may wonder that it is pretty intuitive to use a linear search that traverse list1 to locate the match by comparing each value in list1 with its corresponding index, and we can definitely get the correct output in !(!) time. However, using a linear search for index match has not fully utilized the charming feature of list1 that list1 is a sorted list. We can, by elegantly implementing binary search, reduce the computational complexity of indexMatch to !(!"#$) time. Any ideas? OK. Let’s go back to the example of list1 = [-3, -1, 0, 2, 3, 4, 5, 6, 8, 12, 20] and we add another row in the table which calculates the difference between value and its index as the following.
value -3 -1 0 2 3 4 5 6 8 12 20 index 0 1 2 3 4 5 6 7 8 9 10 value - index -3 -2 -2 -1 -1 -1 -1 -1 0 3 10
After looking at the difference between value and its index, we can easily discover that the list in the 3rd row is also an un-descending list where the position whose corresponding value is 0 exists a match. Note: Adding the 3rd row in the table above never means asking you to create a new list in your code that contains the subtraction results, since only doing the linear subtractions takes linear time, where we want to design some algorithm runs in !(!"#$). Please see the following paragraph to understand what we really need to do in this assignment.
3
And we can further discover that if a certain index is larger than its corresponding value (e.g. index 5 value 4), all the indices which are to the left of the current index cannot contain the targeted match. Similarly, if a certain index is smaller than its corresponding value (e.g. index 9 value 12), all the indices that are to the right of the current index cannot contain the targeted match either. So, with this discovery, we can utilize the binary search algorithm to shrink the search window into half in each iteration, and identify the potential match in !(!"#$) time. 4.2. Index Match Implementation Now, we can open the skeleton code. In the code, the following is the indexMatch function is we need to complete. Input list1 is a sorted list with distinct integers, and the function will return index i for which list1[i] = i. If there is no index that satisfies list1[i] = i, the function should return "No Match Found!".
def indexMatch(list1): global listMedian ### add your code here return ("No Match Found!") # the function should return "No Match Found!" if there is no list1[i] = i
In order to check the functionality of your code, we added a global variable listMedian into the function to save all the medians that having been used in the iterations of the binary search. So, in each iteration, we should append the listMedian with the new median value (the index).
4.3. Multiple Matches In this assignment, you may have another concern, which is, for a list, there can be more than one matches in it, like the following with 5 matches.
value -3 -1 0 2 4 5 6 7 8 12 20 index 0 1 2 3 4 5 6 7 8 9 10
Here, we do not need to worry about the multiple matches cases, returning the first match we discovered should be fine. Note: “The first match we discovered” does not mean the match with the lowest index, but the first match we discovered by using the binary search implementation. 4.4. Some Sample Outputs The following are 3 sample outputs for your reference.
Single Match:
4
Multiple Matches:
No Matches_1:
No Matches_2:
5. Submit your work to Mimir Submit your code to Mimir after you complete your code. Please delete or comment out all the testing codes before your submission (We should only keep the indexMatch function and the global assignment listMedian = []). The Mimir will automatically your submission based on different unit test cases. You can submit your code to Mimir up to 30 times to refresh your existing score before the submission deadline.
1. Introduction In this exercise, we will complete one Python function in order to find a potential indexMatch i for a sorted list with distinct integers in which list[i] = i by using binary search.
2. Objectives The purpose of this assignment is to help you: • Practice binary search. • Refresh knowledge on python lists and functions. Note: Before you start, if you are not familiar with binary search, list or function in Python, you are recommended to review your lecture notes and the additional materials from Dr. Don Sheehy.
3. Background 3.1. Binary Search Binary search is a classic search algorithm which finds the position of a target value within a sorted list.1 In binary search, when we are looking for a particular item in a sorted list, we compare the targeted value with the median of the current list and break the list in half iteratively by keeping the half which may contain the targeted item. So, given a list of length !, the asymptotic running time of the binary search is !(!"#$). The following figure shows the implementation of a binary search for target value 7 on a list with length 17. With binary search, it takes only 4 steps to find target value, which is much faster than linear search asymptotically.
Fig2. 1 Visualization of Binary Search with Target Value Equal to 7
1 Cited from Wikipedia, Binary search algorithm. https://en.wikipedia.org/wiki/Binary_search_algorithm 2 Cited from Wikipedia. https://commons.wikimedia.org/wiki/File:Binary_Search_Depiction.svg#
2
4. Assignment In this assignment, we only need to complete indexMatch function in binary.py. The input of this function is a sorted list list1 with distinct integers. We need to utilize binary search to find out and return a potential index i for which list1[i] = i.
4.1. Index Match using Binary Search In order to have a nice understanding of the binary search implementation in index match, we give an example as the following.
For a certain input,
list1 = [-3, -1, 0, 2, 3, 4, 5, 6, 8, 12, 20]
we can visualize the item values and their corresponding indices as,
value -3 -1 0 2 3 4 5 6 8 12 20 index 0 1 2 3 4 5 6 7 8 9 10
where we can see 8 is the matched index that the indexMatch function should return.
Here, you may wonder that it is pretty intuitive to use a linear search that traverse list1 to locate the match by comparing each value in list1 with its corresponding index, and we can definitely get the correct output in !(!) time. However, using a linear search for index match has not fully utilized the charming feature of list1 that list1 is a sorted list. We can, by elegantly implementing binary search, reduce the computational complexity of indexMatch to !(!"#$) time. Any ideas? OK. Let’s go back to the example of list1 = [-3, -1, 0, 2, 3, 4, 5, 6, 8, 12, 20] and we add another row in the table which calculates the difference between value and its index as the following.
value -3 -1 0 2 3 4 5 6 8 12 20 index 0 1 2 3 4 5 6 7 8 9 10 value - index -3 -2 -2 -1 -1 -1 -1 -1 0 3 10
After looking at the difference between value and its index, we can easily discover that the list in the 3rd row is also an un-descending list where the position whose corresponding value is 0 exists a match. Note: Adding the 3rd row in the table above never means asking you to create a new list in your code that contains the subtraction results, since only doing the linear subtractions takes linear time, where we want to design some algorithm runs in !(!"#$). Please see the following paragraph to understand what we really need to do in this assignment.
3
And we can further discover that if a certain index is larger than its corresponding value (e.g. index 5 value 4), all the indices which are to the left of the current index cannot contain the targeted match. Similarly, if a certain index is smaller than its corresponding value (e.g. index 9 value 12), all the indices that are to the right of the current index cannot contain the targeted match either. So, with this discovery, we can utilize the binary search algorithm to shrink the search window into half in each iteration, and identify the potential match in !(!"#$) time. 4.2. Index Match Implementation Now, we can open the skeleton code. In the code, the following is the indexMatch function is we need to complete. Input list1 is a sorted list with distinct integers, and the function will return index i for which list1[i] = i. If there is no index that satisfies list1[i] = i, the function should return "No Match Found!".
def indexMatch(list1): global listMedian ### add your code here return ("No Match Found!") # the function should return "No Match Found!" if there is no list1[i] = i
In order to check the functionality of your code, we added a global variable listMedian into the function to save all the medians that having been used in the iterations of the binary search. So, in each iteration, we should append the listMedian with the new median value (the index).
4.3. Multiple Matches In this assignment, you may have another concern, which is, for a list, there can be more than one matches in it, like the following with 5 matches.
value -3 -1 0 2 4 5 6 7 8 12 20 index 0 1 2 3 4 5 6 7 8 9 10
Here, we do not need to worry about the multiple matches cases, returning the first match we discovered should be fine. Note: “The first match we discovered” does not mean the match with the lowest index, but the first match we discovered by using the binary search implementation. 4.4. Some Sample Outputs The following are 3 sample outputs for your reference.
Single Match:
4
Multiple Matches:
No Matches_1:
No Matches_2:
5. Submit your work to Mimir Submit your code to Mimir after you complete your code. Please delete or comment out all the testing codes before your submission (We should only keep the indexMatch function and the global assignment listMedian = []). The Mimir will automatically your submission based on different unit test cases. You can submit your code to Mimir up to 30 times to refresh your existing score before the submission deadline.
1 file (262.8KB)
