이진 탐색 (Binary Search)

자료구조의 목적은 데이터를 효율적으로 저장하는 데 있다

이러한 자료구조를 기반으로 작성된 알고리즘은 메모리와 속도를 고려하게 되는데 우리가 더 관심있게 보는 것은 속도이다.

순차 탐색 알고리즘(배열의 첫 번째 원소부터 순서대로 탐색)보다 훨씬 좋은 성능을 보인다

단!!! 배열에 저장된 원소는 정렬되어 있어야 한다

방법

1 배열의 중앙(배열 길이가 n이라고 할 때, (처음0 + 끝n-1)/2)에 찾는 값이 저장되어 있는지 확인

2 만약 아닐 경우, 찾는 값과 배열의 값을 비교하여 찾고자 하는 값이 배열의 값보다 작으면, 배열의 값을 기준으로 오른쪽에 있는 원소들로 탐색 범위 제한

  마찬가지로, 배열의 값보다 찾고자 하는 값이 크면, 배열 값 기준으로 왼쪽에 있는 원소들로 탐색 범위 제한 (오름차순 일 때!)

값을 찾을때까지 계속 반복!

#include<iostream> int BinarySearch(int arr[], int len, int target){ int first = 0; int last = len-1; int mid; while(first <= last){ mid = (first+last)/2; if (target == arr[mid]) return mid; else{ if (target <arr[mid]) last = mid-1; else first = mid+1; } } return -1; //찾지 못했을 때 }

재귀적 구현

#include<iostream> using namespace std; int BinarySearch(int arr[], int first, int last, int target){ if (first > last) return -1; int mid = (first + last) / 2; if (target == arr[mid]) return mid; else{ if (target < arr[mid]) return BinarySearch(arr, first, mid - 1, target); else return BinarySearch(arr, mid + 1, last, target); } }