순차탐색과 이진탐색

---

순차탐색과 이진탐색

---

순환탐색

• 리스트의 첫 원소 부터 좌에서 우로 하나씩 비교한다.

  1. 맨 앞 데이터와 찾으려는 데이터가 같은지 탐색한다.
  2. 데이터가 서로 같지 않다면 다음 데이터와 찾으려는 데이터가 같은지 탐색한다.
  3. 같은 데이터를 찾기 전까지 (2) 과정을 반복한다.

									 # 리스트 구현
def sq_search(arr,n, target):
   									 # 리스트 내 데이터를 차례로 탐색
    for i in range(n):
        if arr[i] == target:
         						     # 비교한 위치 반환(인덱스는 0부터 시작하기 때문에 1 더하기)
            return i + 1 


arr = ["pear","apple","orange"]
									 # 원소 개수
n = len(arr)
 									 # 찾고자 하는 문자열
target = "pear"

print("{}번째에서 데이터 탐색 종료.".format(sq_search(arr,n, target)))

---

이진탐색

• 재귀호출을 이용한 이진탐색

  1. 중간에 있는 숫자를 찾는다.
  2. 중간 숫자와 K를 비교해서 같으면 탐색종료.
  3. K가 작으면, 앞부분에서 동일한 방법으로 탐색, K가 크면 뒷부분에서 동일한 방법으로 탐색한다.
     

def binary_search_recursion(target, start, end, data):
    if start > end:
        return None

    mid = (start + end) // 2

    if data[mid] == target:
        return mid
    elif data[mid] > target:
        end = mid - 1
    else:
        start = mid + 1        

    return binary_search_recursion(target, start, en