4: 알고리즘-1(검색 알고리즘)

배열: 한 자료형안에 여러 값들이 메모리상에 모여 있는 구조 

- 컴퓨터는 모든 숫자를 한 번에 파악할 수 없어서 배열의 인덱스 하나하나에 다 접근함

- 어떤 값이 배열 안에 있는지를 찾아보기 위해서는 배열이 정렬되어 있는지 여부에 따라 여러 방법을 사용할 수 있음

---

선형 검색(Linear Search)

• 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문해 그 값이 속하는지 검사함(처음부터 끝까지 하나씩 순서대로 비교)
• 의사코드로 아래와 같이 나타낼 수 있음

For i from 0 to n-1
 //배열안에 n개의 인덱스가 있고 찾으려는 i요소가 있다.
  If i'th element if 50 //i요소가 50이라면
  
    return true  //True 값 반환

Return false //False값 반환

 

이진 검색(Binary Search)

• 이분 검색이라고도 하며 반으로 나누어서 연산한다는 의미
• 배열이 정렬되어 있으면, 배열 중간 인덱스부터 시작해 찾고자 하는 값과 비교해 그보다 작은(작은 값이 저장되어 있는) 인덱스 또는 큰(큰 값이 저장되어 있는) 인덱스로 이동을 반복함
• 의사코드로 아래와 같이 나타낼 수 있음

If no items

  Return false

If middle item is 50

Return true

Else if 50 < middle item

  Search left half

Else if 50 > middle item

  Search right half

 

https://www.boostcourse.org/cs112/joinLectures/41307

모두를 위한 컴퓨터 과학 (CS50 2019)