バイナリサーチ

探索する

リニアナビゲーション
:すべての要素を順番に参照します.

バイナリナビゲーション
:最小、最大および中間インデックスを検索し、値を最小-中、中-最大インデックスに分けてナビゲートします.

問題)リストLとその中の値xを検索するとき、x値のインデックスを求める(ただし、x値が存在しない場合は-1を返す) 例1) L = [2, 3, 5, 6, 9, 11, 15] x = 6 与えられたパラメータは、L[3]=6であるため、3を返します。 例2) L = [2, 5, 7, 9, 11] x = 4 もしそうであれば、リストLに4の要素が存在しないため、-1を返します。

プール)
配列の最大、最小、および中間値を計算し、x値のインデックスが見つかるまで繰り返します.

ていこうりつ

def solution(L, x):
    answer = -1
    
	# 배열을 순차적으로 순회하며 원하는 값(x)이 나올 때 까지 계속 탐색한다.
	# 하지만, 원하는 값이 배열의 가장 끝에 있으면 낭패;;;
	for index, element in enumerate(L) :
		if element == x:
			answer = index
    
    return answer

効率性(バイナリ)

def solution(L, x):
    answer = -1
    lower = 0
    upper = len(L) - 1
    
    # 최대, 최소 값을 셋팅하고, 중간 값을 계산하여 x값의 인덱스를 구한다.
    while lower <= upper :
    	# x값이 최대, 혹은 최소값 부근에 존재하는 경우를 대비
        middle = lower + (upper - lower) // 2

        if L[middle] == x:		# x값을 찾을 경우.
            answer = middle
            break
        elif L[middle] < x:		# x값이 배열의 오른쪽에 있다면, 최소값을 조정
            lower = middle + 1
        else:				# x값이 배열의 왼쪽에 있다면, 최대값을 조정
            upper = middle - 1

    return answer

有効(バイナリ)-関数を呼び出すために最小(l)パラメータと最大(u)パラメータを追加します。

def solution(L, x, l, u):
    if l > u:
        return -1
    mid = (l + u) // 2
    if x == L[mid]:
        return mid
    elif x < L[mid]:
        return solution(L, x, l, mid - 1)
    else:
    	return solution(L, x, mid + 1, u)

出典:Programmers講座「いらっしゃいませ!資料構造とアルゴリズムは初めてですよね?」