Binary Search(이진탐색)

Basic Concept

---

Binary Search locates a key x in a stored nondecreasing order array by first comparing x with the middle item of the array. If they are equal, the algorithm is done. If not, the array is divided into two subarrays, one containing all the items to the left of the middle item and the other containing all the items to the right. If x is smaller than the middle item, this procedure is then applied to the left subarray. Otherwise, it is applied to the right subarray. If they are equal, the algorithm is done. If not, the subarray is divided in two. This procedure is repeated until x is found or it is determined that x is not in the array.

 

Example The steps done when sorting with Binary Search. (x=18)

 

👉 이진탐색은 오름차순으로 정렬된 배열에서 x를 찾기 위해 먼저 배열의 중간 항목과 값을 비교한다. 값이 동일하면 알고리즘은 종료되지만 그렇지 않은 경우에는 x를 기준으로 해당 배열을 두 개의 하위배열로 나눈다.

x가 중간 항목보다 작으면 왼쪽 하위배열에, 큰 경우 오른쪽 하위배열에 위의 절차를 적용한다. 값이 일치하면 알고리즘은 완료되지만 그렇지 않은 경우에는 이 절차를 x가 발견되거나 x가 배열에 없다고 판단될 때까지 계속 반복한다.

 

 

Binary Search Algorithm

---

Algorithm Design

If x equals the middle item, quit. Otherwise:

1. Divide the array into two subarrays about half as large. If x is smaller than the middle item, choose the left subarray. If x is larger than the middle item, choose the right subarray.
2. Conquer(solve) the subarray by determining whether x is in that subarray.
3. Unless the subarray is sufficiently small, use recursion to do this. Obtain the solution to the array from the solution to the subarray.

 

Pseudo Code

• Binary Search Recursive

// Binary Search (Recursive)
index binsearch(index low, index high)
// Problem: Determine whether x is in the sorted array S of size n.
// Inputs: positive integer n, sorted array of keys S indexed from 1 to n, a key x.
// Outputs: location, the location of x in S (0 if x is not in S).
{
    index mid;

    if (low > high) // stopping case
        return 0;
    else
    {
        mid = (low + high) / 2;

        if (x == S[mid])
            return mid;
        else if (x < S[mid])
            return binsearch(low, mid - 1); // left subarray
        else
            return binsearch(mid + 1, high); // right subarray
    }
}

 

• Binary Search Iteration

// Binary Search (Iteration)
void binsearch(int n, const keytype S[ ], keytype x, index& location)
// Problem: Determine whether x is in the sorted array S of size n.
// Inputs: positive integer n, sorted array of keys S indexed from 1 to n, a key x.
// Outputs: location, the location of x in S (0 if x is not in S).
{
    index low, high, mid;

    low = 1;
    high = n;
    location = 0;

    while (low <= high && location == 0)
    {
        mid = (low + high) / 2;
        if (x == S[mid])
            location = mid;

        else if (x < S[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }
}

 

Source Code

• binsearch.h

// File: binsearch.h
#ifndef BINSEARCH_H
#define BINSEARCH_H

namespace algorihtms
{
    void binsearch1(const int S[ ], int first, int size, int target,
                    bool& found, int& location);
    // Problem: Determine whether x is in the sorted array S of size n.
    // Inputs: positive integer n, sorted array of keys S indexed from
    // 1 to n, a key x.
    // Outputs: location, the location of x in S (0 if x is not in S).

    void binsearch2(const int S[ ], int size, int target,
                    bool& found, int& location);
    // Problem: Determine whether x is in the sorted array S of size n.
    // Inputs: positive integer n, sorted array of keys S indexed from
    // 1 to n, a key x.
    // Outputs: location, the location of x in S (0 if x is not in S).
}

#endif

 

• binsearch.cpp

// File: binsearch.cpp
// Binary Search Iteration
# include "binsearch.h"

namespace algorihtms
{
  // Binary Search (Recursive)
  void binsearch1(const int S[ ], int first, int size, int target, 
                  bool& found, int& location)
  {
    int mid;

    if (size == 0)
      found = false;
    else
    {
      mid = first + size/2;
      if (target == S[mid])
      {
        location = mid;
        found = true;
      }
      else if (target < S[mid])
        // The target is less than S[mid], so search before the mid
        binsearch1(S, first, size/2, target, found, location);
      else
        // The target must be greater than S[mid], so search after the mid
        binsearch1(S, mid+1, (size-1)/2, target, found, location);
    }
  }

  // Binary Search (Iteration)
  void binsearch2(const int S[ ], int size, int target, 
                  bool& found, int& location)
  {
    int low, high, mid;

    low = 0;
    high = size;
    location = 0;
    found = false;

    while (low < high && location == 0)
    {
      mid = (low + high) / 2;
      if (target == S[mid])
      {
        location = mid;
        found = true;
      }
      else if (target < S[mid])
        high = mid - 1;
      else
        low = mid + 1;
    }
  }
}

 

• searchtest.cpp

// File: searchtest.cpp
#include <cstdlib>    // Provides EXIT_SUCCESS
#include <iostream>   // Provides cin, cout
#include "binsearch.h"
using namespace std;
using namespace algorihtms;

int main( )
{
    const int MANY = 13;
    int example[MANY] = {10, 12, 13, 14, 18, 20, 25, 27, 30, 35, 40, 45, 47};
    int target = 0;
    int location = 0;
    bool found = false;

    target = 25;
    binsearch1(example, 0, MANY, target, found, location);

    if (found)
        cout << target << " is at ["
             << location << "] in my array." << endl;
    else
        cout << target << " does not exists." << endl;

    target = 18;
    binsearch2(example, MANY, target, found, location);

    if (found)
        cout << target << " is at ["
             << location << "] in my array." << endl;
    else
        cout << target << " does not exists." << endl;

    return EXIT_SUCCESS;
}

 

 

Time Complexity Analysis

---

Basic operation

the comparison of x with S[mid]

 

Input size

n, the number of items in the array

 

Worst-Case Time Complexity

$W(n) = logn + 1 \in  \Theta (logn)$