Binary Search Algorithm (이진 탐색 알고리즘)

* Binary Search Algorithm(이진 탐색 알고리즘)

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 이진 탐색 알고리즘을 사용하기 위해선 반드시 오름차순으로 정렬이 되어 있는 리스트라는 전제 조건이 필요하다. 

 1. 중앙 원소와 찾고자 하는 X를 비교한다. 

 2-1. 만약 중앙 원소가 찾고자 하는 원소와 같다면 해당 원소 리턴

 2-2. X가 중앙 원소보다 크다면 배열의 우측을 대상으로 탐색 재실행, 작다면 좌측을 대상으로 탐색 재실행

 

* 시간 복잡도

탐색하고자 하는 원소가 N개라면, 첫 시도에는 N개의 원소를, 두번째 시도에는 N/2개의 원소를, 세번째 시도에는 N/4의 원소를 탐색할 것이다. 자료의 갯수가 N개라면 시행 횟수는 밑이 2인 log2N이다. 따라서 시간복잡도는 O(logN)이 된다. 

 

* 소스 코드

- Psuedo Code -

binarySearch(A[0..N-1], value) {//k
  low = 0
  high = N - 1
  while (low <= high) {
      mid = (low + high) / 2
      if (A[mid] > value)
          high = mid - 1
      else if (A[mid] < value)
          low = mid + 1
      else
          return mid // found k
  }
  return -1 // not found k
}

 

 

- JAVA -

// Java implementation of iterative Binary Search
class BinarySearch {
    // Returns index of x if it is present in arr[],
    // else return -1
    int binarySearch(int arr[], int x)
    {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
 
            // Check if x is present at mid
            if (arr[m] == x)
                return m;
 
            // If x greater, ignore left half
            if (arr[m] < x)
                l = m + 1;
 
            // If x is smaller, ignore right half
            else
                r = m - 1;
        }
 
        // if we reach here, then element was
        // not present
        return -1;
    }
 
    // Driver method to test above
    public static void main(String args[])
    {
        BinarySearch ob = new BinarySearch();
        int arr[] = { 2, 3, 4, 10, 40 };
        int n = arr.length;
        int x = 10;
        int result = ob.binarySearch(arr, x);
        if (result == -1)
            System.out.println("Element not present");
        else
            System.out.println("Element found at "
                               + "index " + result);
    }
}

 

참고 - https://www.geeksforgeeks.org/binary-search/