[2주차] 이진 탐색

[hanana1253]

가보자고~

[hanana1253]

이진 탐색

1. 문제 정의

대상 목록과 목푯값의 일치 여부를 확인해야 할 때

2. 선형 스캔

• 리스트에서 한 번에 하나씩 값을 목푯값과 비교하면서 목푯값을 찾거나 목록의 끝에 도달할 때까지 비교해 목푯값을 찾음
• 무식한 검사 (각각의 비교를 조금이나마 최적화할 순 있지만) 자료구조에 다해 아무것도 모른다면 프로세스 최적화 불가

3. 이진 탐색 알고리즘

• "정렬된" 리스트에서 목푯값 찾을 때 작동
  • 배열이 오름차순 등으로 정렬되어 있음을 이용
• 현재 탐색 공간의 중앙값을 선택하며 시작
• 상계나 하계가 아닌 중간 지점이 목푯값을 가리킬 때까지 탐색
• 없는 값 여부는 모두 탐색한 후에야 알 수 있다
• 이진 탐색 구현: while과 상계/하계 인덱스 및 중앙값으로 구현

4. 이진 탐색 적용하기

• 더 나은 정밀도를 얻을 수 있다.
• 이분법 알고리즘에 적용

5. 실행 시간

• 목푯값이 리스트 시작지점에 있거나 리스트가 작다면 선형 탐색이 더 효율적
• 최악의 성능을 비교하는 빅오 표기법으로는 선형 탐색은 선형적으로, 이진 탐색은 로그적으로 비교횟수 증가
• 충분히 큰 리스트에 대해 원소 개수의 로그만큼만 비교하면 된다.

6. 이진 탐색이 중요한 이유

• 문제 자체의 구조(정렬되어 있다는 데이터의 특성) 활용
• 선형 함수에서 로그 함수로 "최악의 경우 실행 시간"을 줄임

느낀점

• 이사람 왜 근데 1장부터 빌드업도 없이 커피타령을 자꾸 하는거지...? 내가 모르는 서문이 있었나..?
• "계산적 사고의 가장 기본적인 개념인 문제 자체의 구조를 활용해 효율적인 해법을 구축한다"는 말이 좀 멋있다

[ella-yschoi]

ㅋㅋㅋㅋㅋㅋㅋㅋ 서문엔 그런 내용이 없었던 것 같은데! 제레미 쿠비카가 커피를 좋아하시나봐요

[sa02045]

9쪽에

"주어진 자료 구조는 어떻게 계산을 가능하게 하는가? .....중략..... 왜 필자는 커피에 굉장히 집착하는가?

이러한 질문에 대답하면 자료 구조를 효과적으로 사용하는 역량을 기를 수 있고, 이는 곧 미래에 새로운 기술을 개발하는 데 필요한 밑거름이 되어줄 것입니다."

라고 하네요 하하

[hanana1253]

역시 책을 샅샅히 읽는 승희님은 답을 알고계시군요

[ella-yschoi]

역시.....

[sa02045]

• 이 장에서 중요하다고 느낀 문장
  • 효율적인 알고리즘이란 데이터의 정보, 데이터의 구조를 활용하는 것!
• 이진탐색
  • 정렬된 데이터에서 원하는 값을 찾는 효율적인 방법은 무엇일까?
  • 노가다로 하나하나 찾을 수도 있지만(브루트 포스) 효율적인 방법이 무엇일까?를 고민하는 것이 바로 알고리즘이다.
• 이진탐색 접근방식은 “이산적” 데이터 말고도 “연속” 데이터에도 적용할 수 있다.
  • 예시) 완벽한 커피를 만드려면?
  • 이진탐색을 사용하면 더 나은 정밀도를 얻을 수 있음 → 이분법(bisection search)의 기초, f(x) =0인 x값을 찾기 위해 사용
• 실행시간
  • 알고리즘 실행 시간을 Big-O 표기법, 측정법으로 표현한다.
  • 데이터 크기가 증가함에 따라 알고리즘 “평균” 실행 시간은 어떻게 변하는가?
  • 데이터 크기가 증가함에 따 알고리즘 “최악의 경우” 실행 시간이 어떻게 변하는가?
    • 노가다(선형스캔, 브르투포스) ⇒ 데이터 크기에 따라 선형적으로 증가
    • 이진탐색 ⇒ 데이터 크기의 log 로그적으로 증가

function binarySearch(arr, target){
   let upper = arr.length - 1
   let lower = 0
	  
	  while(lower <= upper){
		  let mid = Math.floor((lower + upper) / 2)
		  
		  if(arr[mid] === target){
			  return mid
		  }
		  
		  if(arr[mid] < target){
			  lower = mid + 1
		  } else {
			  upper = mid - 1
		  }
	  }
	  
	  return -1
}

[ainochi-kor]

이진 탐색 알고리즘을 구현하면서 읽혀지는게 신기했습니다!
이진 탐색

[ella-yschoi]

저도 커피를 참 좋아하지만, 저자만큼 진심은 아닌 것 같아요
아무튼.. 이진 탐색을 선형 탐색과 비교해 동작 원리, 시간 복잡도를 더 잘 이해할 수 있었습니다!

정리는 여기 👉 02_이진_탐색.md

[yunseorim1116]

02주차
이진 탐색은 알고리즘 단골 유형이라 이론으로 읽으니 엄청 흥미로웠어요

[sunhpark42]

• 이진탐색 방식을 실수 범위에도 적용하는 것이 신선했다.
• 탐색, 정렬을 할 때 데이터의 특성을 고려하는 것도 중요하겠구나 하는 생각이 들었다.
• 오늘의 문장: "정렬돼 있다는 데이터의 특성을 활용함으로써 최악의 경우 실행 시간을 리스트 크기에 대한 선형 함수에서 로그 함수로 줄일 수 있다. 이 실행 시간의 차이는 데이터가 커질수록 훨씬 더 커진다."
• 3장은 동적자료구조던데, 재밌을 것 같다.

[thgr8ganzi]

정리

이진탐색 알고리즘이 정렬되어야 작동한다는걸 까먹고있었는데 깨워줘서 고마웠습니다

[chloe-codes1]

내용 정리

선형 스캔

• 탐색 방식
  • list에서 한 번에 하나씩 값을 비교하면서 목푯값을 찾거나, 목록의 끝에 도달할 때까지 비교해 목푯값을 찾는다
• 단점
  • 원소가 아주 많은 리스트에서 비효율적이다

이진 탐색 알고리즘

• 탐색 방식

  • list를 반으로 분할하고, 목푯값이 어느쪽 절반에 속하는지 결정한다
  • 목푯값이 포함되지 않는 절반을 버리고, 여전히 목푯값이 있을 수 있는 나머지 절반만 가지고 같은 과정을 반복해 마지막 값만 남을때까지 이를 반복한다

• 특징

  • 정렬된 데이터에서만 작동한다
  • 배열이 오름차순으로 정렬되어 있음을 이용한다
  • 두 경계를 이용해 탐색 공간을 추적한다
    • upper bound → index high
    • lower bound → index low
  • index low가 목푯값을 가리키게 되어도, 중간 지점이 목푯값을 가리킬 때까지 탐색을 계속한다

• 없는 값 처리

  • 목푯값이 리스트에 없는 경우 탐색을 계속 진행하다 보면, 두 경계 중 하나가 항상 중간 index를 넘어가기 때문에 index high < index low 가 되면 탐색을 중단할 수 있다

• 구현

  def binary_search(array: list[int], target: int) -> int:
    start, end = 0, len(array) - 1
  
    while start <= end:
      mid = (start + end) // 2
  
      if array[mid] == target:
        return mid
      elif array[mid] < target:
        start = mid + 1
      else:
        end = mid - 1
  
    return -1

• index 나 이산적인 원소 집합이 존재하지 않는 연속 데이터에 적용

  • 탐색 방식
    • index 대신 값에 대한 upper bound와 lower bound를 이용
    • 범위가 작아질 때 탐색을 종료
      • upper bound - lower bound < threshold
  • 시사점
    • 선형 스캔보다 더 나은 정밀도를 얻을 수 있다
    • 이분법 (bisection search) 등의 수학적 기술의 기초가 된다
      • 이분법은 f(x) = 0인 x 값을 찾기 위해 사용하는데, 0보다 크거나 작은 경계를 추적한다
      • 중앙값에서 구간을 반복하여 절반으로 나눔으로써, 이분법 알고리즘은 함수가 정확히 0이 되는 x값에 접근할 수 있따

• 실행 시간

  	Time Complexity	Space Complexity
  선형 스캔	O(n)	O(1)
  이진 탐색	O(log⁡ n)	O(1) → 반복문 / O(log⁡n) → 재귀

  단, 이진 탐색은 정렬되지 않은 경우 데이터 정렬이 먼저 필요하므로 O(n log n)의 추가 비용 발생

생각

• 오늘 leetcode 에서 binary search 문제 풀었는데 이 내용이 책에 나와서 재밌었다
• 자세히 살펴볼 수 있어 좋았다