CodeItのアルゴリズムの定式化課を聞いて整理した文章

1.一つの問題を解決するための多様な方法

ロミオとジュリエットの本を探しています.どんな方法がいいですか.

から、右側から一つずつ出して、「ロミオとジュリエット」であることを確認.

本をアルファベット順に整理すると?

の中間点の本を選択します.

で検索したタイトルと選択したタイトルの最初のアルファベットを確認します.

基、右の全書を除く.

欲しい本が見つかるまで繰り返す.いろいろな方法を考えて、どの方法がもっと良いかを分析するのはアルゴリズムを学ぶことです.

2.線形検索とバイナリ検索

私たちは図書館で本を探す方法を調べた.これらの問題はプログラミングで「探索問題」と呼ばれている.
≪ナビゲート｜Navigate｜ldap≫:保存された情報から必要な値を検索します.

ナビゲーションアルゴリズム

線形検索アルゴリズムとバイナリ検索アルゴリズムを使用して検索します.

リニアサーチアルゴリズム(Linear Search Algorithm):1つずつすべて検索します。

2から順にデータの検証を開始します.

29が見つかったら、もう見る必要はなく、探索を終了します.

バイナリ検索アルゴリズム(binary search algorithm):中間値をチェックし、半減して検索します。

の中間値を確認します.確認は19です.

の29が19より大きいことを探して、19以下の数字は除外することができます.

の残りの数字で中間値を再確認します.調べたら37です.

の29が37未満であることを検索するには、37以上の数字を除外することができます.

の残りの数字で、中間値が29であることを調べてみました.私たちが欲しい値段を見つけました.

私たちは同じ問題を解決して、2つの解決方法を見つけた.どの方法が有効か考えてみましょう.

3.リニアナビゲーションの実施を試みる

線形検索アルゴリズムを使用して、リストに含まれる要素を決定します.
パラメータとして入力したelementでは、someリストは参照する値と検索するリストです.
elementが見つかった場合はその場所(インデックス)を返し、存在しない場合はNoneを返します.

# 구현 코드
def linear_search(element, some_list):
    pass

print(linear_search(2, [2, 3, 5, 7, 11]))
print(linear_search(0, [2, 3, 5, 7, 11]))
print(linear_search(5, [2, 3, 5, 7, 11]))
print(linear_search(3, [2, 3, 5, 7, 11]))
print(linear_search(11, [2, 3, 5, 7, 11]))

# 실행 결과
0
None
2
1
4

私の答え

# 구현 코드
def linear_search(element, some_list):
    for i in range(len(some_list)):
        if some_list[i] == element:
            return i

print(linear_search(2, [2, 3, 5, 7, 11]))
print(linear_search(0, [2, 3, 5, 7, 11]))
print(linear_search(5, [2, 3, 5, 7, 11]))
print(linear_search(3, [2, 3, 5, 7, 11]))
print(linear_search(11, [2, 3, 5, 7, 11]))

for文を使用してsome listからelementをナビゲートし、関数の終了時にreturnが指定されていない場合はNoneを返します.したがって、returnは個別に指定されていません.

4.バイナリナビゲーションの実装を試みる

バイナリ検索アルゴリズムを使用して、リストに含まれる要素を決定します.
バイナリ・ナビゲーションは、ソートされたリストを前提とします.△そうしてこそ適用できる.
elementが見つかった場合はその場所(インデックス)を返し、存在しない場合はNoneを返します.

# 구현 코드
def binary_search(element, some_list):
    pass

print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))

# 실행 결과
0
None
2
1
4

私の答え

def binary_search(element, some_list):
    left = 0
    right = len(some_list)-1
    while True:
        if left>right:  # 시작, 끝 인덱스가 역전되면 None을 반환
            return None
        
        center = (left + right) // 2  # 중간값에 대한 인덱스 구하기
        if some_list[center] == element:  # element를 찾았으면 반환
            return center

        if element > some_list[center]:  # 중간값보다 element가 크면 왼쪽은 제외
            left = center + 1
        else:  # 중간값보다 element가 작으면 오른쪽은 제외
            right = center - 1
                

print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))

正解

def binary_search(element, some_list):
    start_index = 0
    end_index = len(some_list) - 1
    
    while start_index <= end_index: # while문의 반복 조건으로 시작 인덱스와 마지막 인덱스가 역전되지 않았을 때만 동작
        midpoint = (start_index + end_index) // 2
        if some_list[midpoint] == element:
            return midpoint
        elif some_list[midpoint] > element:
            end_index = midpoint - 1
        else:
            start_index = midpoint + 1
    return None

print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))

->while文の繰り返し条件は、開始インデックスと最後のインデックスが逆転しない場合にのみ機能します.これにより、重複文内のコードが減少します.