Python - 알고리즘 (선형검색,이진검색)

2024. 2. 26. 14:19·IT/Python
목차
  1. 선형검색
  2. for 문으로
  3. 이진검색

선형검색

  • 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다.
datas = [3,2,5,7,9,1,0,8,6,4] print(f'datas: {datas}') print(f'datas length : {len(datas)}') searchData = int(input('찾으려는 숫자 입력 : ')) searchResultIdx = -1 n = 0 while True: if n == len(datas): searchResultIdx = -1 break elif datas[n] == searchData: searchResultIdx = n break n += 1 print(f'searchResultIdx : {searchResultIdx}')

문제풀이 :
len(datas)까지 n이 계속 증가하면서 숫자를 찾는데 만약 len(datas)에 도달했다면
리스트에서 원하는 숫자를 찾지 못했다는 의미로 -1을 출력
만약 len(datas)범위 안에서 원하는 숫자 찾으면 그 숫자의 위치(인덱스) 출력

여기서
if n == len(nums):을 먼저 사용하는 이유는
n이 리스트의 길이와 같아지기전에 검사를 종료해야하기 떄문

for 문으로

  • 중복숫자 인덱스 위치 뽑기
nums = [4,7,10,2,4,7,0,2,7,3,9] n = 0 resultNums = [] Find = int(input('찾을 수 : ')) for i in range(len(nums)): if Find == nums[i]: print(nums[i]) resultNums.append(i) print(resultNums)

이진검색

  • 정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다.
    (검색 범위를 점차 좁혀 나가면서 찾아나가는 방식)
datas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # 정렬이 되어있다는 기본 전제하에 이진검색 print(f'datas: {datas}') print(f'datas length : {len(datas)}') searchData = int(input('search data: ')) searchResultIdx = -1 # 초기화 staIdx = 0 endIdx = len(datas) -1 midIdx = (staIdx + endIdx) // 2 midVal = datas[midIdx] print(f'midIdx: {midIdx}') #중앙 인덱스값 print(f'midVal: {midVal}') # 중앙값 while searchData <= datas[len(datas)-1] and searchData >= datas[0]: # 범위밖으로 나가는거 막는거 ​​​​if searchData == datas[len(datas)-1]: # 찾는값이 ​​​​​​​​searchResultIdx = len(datas) - 1 ​​​​​​​​break ​​​​if searchData > midVal: ​​​​​​​​staIdx = midIdx ​​​​​​​​midIdx = (staIdx + endIdx) // 2 ​​​​​​​​midVal = datas[midIdx] ​​​​​​​​print(f'midIdx: {midIdx}') #중앙 인덱스값 ​​​​​​​​print(f'midVal: {midVal}') # 중앙값 ​​​​elif searchData < midVal: #가운데값보다 작은경우 (데이터가 왼쪽) ​​​​​​​​endIdx = midIdx ​​​​​​​​midIdx = (staIdx +endIdx) // 2 ​​​​​​​​midVal = datas[midIdx] ​​​​​​​​print(f'midIdx: {midIdx}') #중앙 인덱스값 ​​​​​​​​print(f'midVal: {midVal}') # 중앙값 ​​​​elif searchData == midVal: ​​​​​​​​searchResultIdx = midIdx ​​​​​​​​break print(f'searchResult: {searchResultIdx}')

문제풀이 :

searchData <= datas[len(datas)-1] and searchData >= datas[0]:을 사용하여 범위를 지정해주고
midVal를 기준으로 나눠서 찾아나가는거

반응형
저작자표시 비영리 변경금지 (새창열림)

'IT > Python' 카테고리의 다른 글

Python - 알고리즘 (버블정렬,삽입정렬,선택정렬)  (1) 2024.02.26
Python - 알고리즘 (순위)  (0) 2024.02.26
Python - 자료구조  (0) 2024.02.22
[Python] 동시성 프로그래밍과 병렬성 프로그래밍  (1) 2024.02.19
[Python] __name__  (2) 2024.02.14
  1. 선형검색
  2. for 문으로
  3. 이진검색
'IT/Python' 카테고리의 다른 글
  • Python - 알고리즘 (버블정렬,삽입정렬,선택정렬)
  • Python - 알고리즘 (순위)
  • Python - 자료구조
  • [Python] 동시성 프로그래밍과 병렬성 프로그래밍
생각 기록실
생각 기록실
AI(LLM)와 서비스 기획을 공부하며 작성하는 기술 블로그입니다. (feat. 영화리뷰를 곁들인..)
    반응형
  • 생각 기록실
    이러쿵 저러쿵
    생각 기록실
  • 전체
    오늘
    어제
  • 링크

    • Github
    • LindeIn
    • 분류 전체보기 (115)
      • 이러쿵 저러쿵 (5)
      • 정보통계 (7)
        • 데이터마이닝 (2)
        • 금융공학 (4)
      • IT (26)
        • Python (10)
        • AWS (5)
        • Github (2)
        • Project (8)
      • 리뷰 (29)
        • 영화 (22)
        • 책 (7)
      • 기타 (48)
  • hELLO· Designed By정상우.v4.10.3
생각 기록실
Python - 알고리즘 (선형검색,이진검색)

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.