Herkese iyi forumlar arkadaşlar. İnternette bir soruyla karşılaştım (ingilizce) ve buraya atıp sizlere sormak istedim.
Yazılı olarak soru :
Supose that initially we had two identical (all elements are same) lists consisting of unique integers, sorted increasingly. Let’s call these lists as list_a and list_b. Someone randomly deleted
an element from list_b and appended an element to the end that is greater than the last element
of list_b. Then, the two elements of the two lists will be same upto the index that is deleted and
for the rest of indices the two lists will have unequal elements in the same indices. For example,
consider the two lists below:
[1, 6, 8, 9, 14, 16, 19, 21, 26, 31, 34, 35, 37, 38, 41, 42, 44, 47, 49, 53]
#list _a
[1, 6, 8, 9, 14, 16, 19, 21, 23, 26, 31, 34, 35, 37, 38, 41, 42, 44, 47, 49]
#list _b
list_a[i] = list_b[i] for, $i=0,. . . ,7 $ and list_a[i] is different form list_b[i] for all i ≥ 8.
Starting from 0, the first index that two lists have different value is called divergence index. The
divergence index for this example is 8.
Write a recursive method that finds the divergence index of two lists in O(log n) complexity using
bi-section.
Notes: Remember how we solved the “guess what number I have in my mind” game in the class.
Answers with for-loops that traverse through the all elements from the beginning to end (or, from
the end to the beginning etc.) are not valid.
def div_index(a, b):
# ... This is where you will write your code
# ... call somewhere div_index ...
# ...
pass
# Run the test case:
list_a = [1, 6, 8, 9, 14, 16, 19, 21, 26, 31, 34, 35, 37, 38, 41, 42, 44, 47,␣
, →49, 53]
list_b = [1, 6, 8, 9, 14, 16, 19, 21, 23, 26, 31, 34, 35, 37, 38, 41, 42, 44,␣
, →47, 49]
div_index(list_a, list_b)
# You should get 8
Fotoğraf olarak soru :
Yardımcı olmaya çalışan arkadaşlara şimdiden teşekkürler.