Binary Search 이진검색/탐색 알고리즘

moontag·2022년 4월 11일
0
post-thumbnail






Algorithm 알고리즘

  • 문제 해결을 위한 단계적 절차/스텝들이다.
    "몇 초" 같은 시간 단축이 아니라, 단계를 말한다. 단계가 적을 수록 효율적인 알고리즘이다
  • Time Complexity 시간 복잡도 존재
    입력 데이터의 개수에 따라 실행되는 알고리즘의 단계의 수를 의미한다.



왜 필요한가

  • Array에서는 데이터 읽기가 빠르지만, 검색, 삽입, 삭제할 때는 느리다.
    그래서 효율적인 알고리즘을 사용하면 빨라질 수 있다. 이러한 한계점을 극복하기 위해 Search Algorithm을 살펴보고자 한다


Linear Search 선형검색 알고리즘

인덱스 0부터 끝까지 순서대로 검색한다

  • 가장 기본적인 방법
  • 아이템을 추가하는 것은 빠르다
  • 배열이 커지면 검색하는 것이 느려진다
  • * Linear Time Complexity 선형 시간복잡도
    배열이 커지면 검색하는 시간이 길어지는 것



Binary Search 이진검색 알고리즘

  • 탐색할 범위를 절반부터 시작해서 원하는 값을 검색한다
    ex) 1234567 중 3찾기
    : 중간값 4부터 시작. 4보다 값이 작으면 123 중 2 선택, 2보다 크면 3선택해서 찾음
  • 모든 배열에 쓸 수 없고 Sorted Array 정렬된 배열에서만 사용 가능하다
  • 거대한 배열에서 효과적이다
  • 검색 시 정렬안된 경우보다 빠르다
  • 하지만, 아이템 추가시 시간이 소요된다
  • * Sorted Array 정렬된 배열
    아이템 추가하는 것은 정렬안된 경우보다 시간이 더 걸린다
    그런데 검색하는 것은 정렬안된 경우보다 훨씬 빠르다
profile
터벅터벅 나의 개발 일상

0개의 댓글