Linear Search 선형탐색

• 선형탐색은 오름차순이나 내림차순으로 되어 있는 배열 (dictionary나 list)에서 for문을 사용해 목표물이 나올 때까지 찾는 방법
• 배열의 첫번 째 수가 나의 목표물인 경우에는 연산을 단 한번만 하면 된다! 하지만 1000개의 요소가 있는 리스트의 맨큼에 내 목표물이 있다면? 효율적이지 않다. 복삽한 연산이 포함되어 있는 탐색이라면 훨씬 덜 효율적!
• 그렇다면 무조건 리스트의 중간에서 탐색을 시작해보면 어떨까? --> 이진 탐색

Binary Search 이진탐색

• 우선 리스트를 정렬한다. 그리고 리스트의 중간에서 내 목표물보다 큰 수가 위치한 방향을 찾는다. 해당 방향의 중간지점에서 같은 작업을 수행한다.
• 이 작업을 수행할 때마다 탐색할 자료의 개수는 절반씩 사라진다. 선형탐색에 비해 훨씬 빠르고 효율적으로 목표물을 찾을 수 있는 것이다.

Time Complexity 시간복잡도

• 이진탐색을 반복할 때마다 마저 탐색을 해야하는 자료의 개수는 반씩 사라진다. 자료의 수가 N이라고 할 때 첫 탐색 시에는 N/2가 버려지고 그 이후로부터는 1/2씩 사라지기 때문에 탐색을 k번 시행했을 때 내가 탐색한 자료의 개수는 ((1/2)^k)N이다. 탐색이 끝나는 시점에서 최악의 경우에는 남은 자료가 한개가 된다는 점을 생각했을 때 ((1/2)^k)N ≈ 1이며 이를 로그화하여 생각해보면 K ≈ log2 N이 된다. 즉, 자료의 갯수 N에 따른 시행 횟수는 log2 N가 된다.
• 알고리즘의 복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 쓰이는 Big O notation (점근 표기법). Big O notation을 이용해 시간 복잡도를 나타낼 수 있는데 O(N)이고 이를 Big 0의 N이라 말한다. 이 말은, 이진탐색의 경우 최악의 상황에서는 log2 N번의 비교를 수행해야 한다는 것이다.
• 선형탐색의 경우 최악의 경우 O(N)이기 때문에 대부분의 경우 binary search 시행 시에 훨씬 빠르다는 것을 알 수 있다.

이진탐색을 구현해보자

import math

def search(nums, target):  
  nums.sort()
  halfway = len(nums)//2
  ans = nums[halfway]
  loop = 0

  while ans != target:
    if nums[halfway-1] >= target:
      ans = nums[halfway-1]
      halfway //= 2
    elif nums[halfway] <= target:
      halfway += (halfway // 2)
      ans = nums[halfway]

    loop += 1
    if loop > math.log(len(nums), 2):
      halfway = -1
      break
    
  return halfway