ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Binary Serach
    알고리즘 2020. 3. 16. 20:57

    Binary Search 이진탐색

    • 순차 탐색 : 처음부터 끝까지 하나씩 모든 데이터를 체크하여 값을 찾는 방법.
    • 이진 탐색 : 탐색 범위를 절반씩 줄어가며 값을 찾는 방법. 탐색 전, 배열이 미리 정렬되어 있어야한다.

    배열의 크기가 N이라고 할때,


    순차탐색 

     이진탐색

     시간복잡도

     O(N)

     O(log N)


    • 탐색 방법

     크기가 N인 배열 arr에서, target을 찾는다고 가정 시
    1. start = 0, end = N-1 로 초기화 한다.
    2. mid = (start + end) / 2 로 초기화 한다.
    3. target과 arr[mid]의 값을 비교한다. 값이 같을 시, 탐색을 종료
        같지 않을시, target < data[mid] 이면 end = mid-1로 업데이트 후 2번으로 돌아감
                          target > data[mid] 이면 start = mid+1로 업데이트 후 2번으로 돌아감

    • 문제에서 사용할 때의 while문?
        while(end > start)면 start = mid + 1, end = mid
        while(end >= start)면 start = mid + 1, end = mid - 1 


    '알고리즘' 카테고리의 다른 글

    Greedy Algorithm  (0) 2020.03.17
    Floyd-Warshall  (0) 2020.03.17
    Dijkstra  (0) 2020.03.17
    DP  (0) 2020.03.16
    DFS & BFS  (0) 2020.03.16

    댓글

Designed by Tistory.