[알고리즘, GFG]#1_Binary Search, 이진 탐색

 

[알고리즘, GFG]#1_Binary Search, 이진 탐색

 

geeksforgeeks 연습 문제 중 BInary Search(이진 탐색) 문제입니다.

 

---

 

Overview

 

1. 문제
2. 개념
3. 풀이

 

문제

 

풀이

1. 개념

 

• 이진 탐색 알고리즘은 "정렬된 상태"의 데이터 목록에서 특정한 값의 위치를 찾는 알고리즘입니다.
• 기본적으로, 이진 탐색 알고리즘은 배열의 왼쪽 끝(Left), 오른쪽 끝(Right), 그리고 가운데(Mid) Index를 활용합니다.
• 글로 쓰는 것보다 코드를 보는 것이 훨씬 이해하기 쉽기 때문에 자세한 내용은 아래 코드에서 설명하겠습니다.
• 이진 탐색 알고리즘의 시간 복잡도는 O(log n)으로, 선형 탐색보다 빠릅니다.
• 다만, 오직 "정렬된" 상태의 데이터 목록에서만 활용할 수 있습니다. 

 

결과 코드

 

// User function template for C++

class Solution {
  public:
    int binarysearch(int arr[], int n, int k) {
    	// 왼쪽, 즉 첫번째 인덱스
        int left = 0;
        // 오른쪽, 즉 마지막 인덱스
        int right = n-1;
        int ans = -1;
        
        if(arr[left] > k || arr[right] < k)
        {
            return ans;
        }
        
        while(left <= right)
        {
      	    // 루프가 한번 돌 때마다, mid(가운데 인덱스)를 계산합니다.
            int mid = (left+right)/2;
            if(k == arr[mid])
            {
                ans = mid;
                break;
            }
            // k가 arr[mid] 보다 작으면, Right를 땡겨옵니다.
            else if( k < arr[mid])
            {
                right = mid-1;
            }
            // k가 arr[mid] 보다 크면, Left를 땡겨옵니다.
            else
            {
                left = mid+1;
            }
        }
        
        return ans;
    }
};