[PYTHON/COMMON] 리스트에서 이진 탐색(Binary Search)을 사용해 특정 값 인덱스 구하기

■ 리스트에서 이진 탐색(Binary Search)을 사용해 특정 값의 인덱스를 구하는 방법을 보여준다.

▶ 예제 코드 (PY)


def getBinarySearchValueIndex(sourceList, value):
    firstIndex, lastIndex = 0, len(sourceList)

    while firstIndex <= lastIndex:
        middleIndex = (firstIndex + lastIndex) // 2
        if sourceList[middleIndex] == value:
            return middleIndex
        if sourceList[middleIndex] > value:
            lastIndex = middleIndex - 1
        else:
            firstIndex = middleIndex + 1

sourceList = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

valueIndex = getBinarySearchValueIndex(sourceList, 6)

print(valueIndex, sourceList[valueIndex]) # 5 6

def getBinarySearchValueIndex(sourceList, value):

firstIndex, lastIndex = 0, len(sourceList)

while firstIndex <= lastIndex:

middleIndex = (firstIndex + lastIndex) // 2

if sourceList[middleIndex] == value:

return middleIndex

if sourceList[middleIndex] > value:

lastIndex = middleIndex - 1

else:

firstIndex = middleIndex + 1

sourceList = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

valueIndex = getBinarySearchValueIndex(sourceList, 6)

print(valueIndex, sourceList[valueIndex]) # 5 6