問題
リストの中から見つけたい要素と一致する要素のインデックスを返す問題。線形探索の問題。「ランダムに並んでいるリスト」から探索を行う唯一の方法。
実装1
解説は不要なのかもしれませんが、線形探索を行えばよいので、インデックスをインクリメントしながら、一致する要素を探して、一致すればインデックスを返す。見つからない場合は-1を返す。
from typing import List
def linear_search(numbers: List[int], target: int) -> int:
len_numbers = len(numbers)
i = 0
while i < len_numbers:
if numbers[i] == target:
return i
i += 1
return -1
if __name__ == '__main__':
numbers = [6,4,3,2,1,2,8]
print(linear_search(numbers, 2))
3
for文で書き直すとこのようになる。
from typing import List
def linear_search_for(numbers: List[int], target: int) -> int:
len_numbers = len(numbers)
for i in range(len_numbers):
if numbers[i] == target:
return i
return -1
if __name__ == '__main__':
numbers = [6,4,3,2,1,2,8]
print(linear_search_for(numbers, 2))
3
実装2
一致する要素を探して、一致すればインデックスを返すが、リストの中に同じ値があれば、そのインデックスも含めて返すような問題を考える。
from typing import List
def linear_search_for2(numbers: List[int], target: int) -> List[int]:
len_numbers = len(numbers)
result = []
for i in range(len_numbers):
if numbers[i] == target:
result.append(i)
return result
if __name__ == '__main__':
numbers = [6,4,3,2,1,2,8]
print(linear_search_for2(numbers, 2))
[3, 5]