데이터 취업 스쿨 스터디 노트 -(16)알고리즘 연습문제

(6_032) 이진검색
함수 코드
(왜 마지막 숫자가 일치하는 경우를 따로 작성하는지, 존재하지 않는 숫자를 검색하려고 할때 어떻게 무한 루프 방지하는지)

def searchNumberBinary(ns, sn):

    searchResultIdx = -1 #찾으려는 숫자의 인덱스

    #이진 검색의 경우에는 전체 데이터에서 반을 잘라서 크고작음을 비교
    staIdx = 0
    endIdx = len(ns)-1
    midIdx = (staIdx + endIdx) // 2
    midVal = ns[midIdx] #중간값과 크고 작음을 비교해야 하므로

    print(f'staIdx: {staIdx}, endIdx: {endIdx}')
    print(f'midIdx: {midIdx}, midVal: {midVal}')

    while sn >= ns[0] and sn <= ns[len(ns)-1]: #검색 범위 안에 있어야 while문을 돔

        # 운좋게 마지막 숫자와 일치하는 경우.
        # 왜 첫번째 숫자와 일치하는 경우는 안하고 이 경우에만 하냐면
        # 중간값을 2로 나눈 몫으로 구하기 때문에 만약 최종 두개가 남은 상태에서 두 자리의 인덱스값의 중간값을 구하면
        # 결국 작은 인덱스 값만 반복적으로 중간값이됨.ex) 인덱스 (7+8)//2는 7로 무한반복되서 마지막 인덱스에 해당하는 경우가 없음.
        if sn == ns[len(ns)-1]:
            searchResultIdx = len(ns) -1
            break

        #찾으려는 값이 목록에 없을때 무한 루프가 발생한다.
        #이걸 방지하기 위해
        if staIdx + 1 == endIdx:
            if ns[staIdx] != sn and ns[endIdx] != sn:
                break

        if sn > midVal:
            staIdx = midIdx
            midIdx = (staIdx + endIdx) // 2
            midVal = ns[midIdx]
            print(f'+staIdx: {staIdx}, endIdx: {endIdx}')
            print(f'+midIdx: {midIdx}, midVal: {midVal}')

        elif sn < midVal:
            endIdx = midIdx
            midIdx = (staIdx + endIdx) // 2
            midVal = ns[midIdx]
            print(f'-staIdx: {staIdx}, endIdx: {endIdx}')
            print(f'-midIdx: {midIdx}, midVal: {midVal}')

        elif sn == midVal:
            searchResultIdx = midIdx
            break

    return searchResultIdx

실행 코드

import binaryMod

if __name__ == '__main__':

    nums = [1,2,4,6,7,8,10,11,13,15,16,17,20,21,23,24,27,28]
    searchNum = int(input('input search number: '))

    resultIdx = binaryMod.searchNumberBinary(nums, searchNum)
    print(f'nums: {nums}')

    if resultIdx == -1:
        print('No results found')
        print(f'search result index: {resultIdx}')

    else:
        print('>>> Search Result <<<')
        print(f'search result index: {resultIdx}')
        print(f'search result number: {nums[resultIdx]}')

(6_046) 아스키코드 변환 및 확인
if str(data).isalpha(): data값이 알파벳이면.
isaplha()는 문자만 받으므로 data를 문자로 변환해줌.

(6_035) 삽입정렬
바보인가... 머리가 안돌아간다...

(6_043) 최빈값 알고리즘중간 메모

#n:0>3 오른쪽 정렬로 3자리 숫자로 맞추고 없는 숫자는 0으로 채운다    
            print(f'{n:0>3} {maxNumIdx}세 빈도수: {maxNum}\t',end='')