이진 탐색 알고리즘(Binary Search) - 소스코드

이진 탐색 알고리즘의 기본 골격

while(first <= last) // first <= last가 반복의 조건임에 주의하자.

{

 // 이진 탐색 알고리즘 작성

}

int BSearch(int ar[], int len, int target)
{
 int first = 0;
 int last = len-1;
 int mid;
 
 while(first <= last)
 {
  mid = (first+last)/2; // 탐색 대상의 중앙을 검색
  
  if(target == ar[mid]) // 중앙에 저장된 것이 타겟이라면
  {
    return mid; // 탐색 완료
  }
  
  else // 타겟이 아니라면 탐색 대상을 반으로 줄인다.
  {
     if(target < ar[mid]) 
     { last = mid-1; }
 
     else
     { first = mid+1; }
   
  }
 
  
 }
 return -1;
}
 

first는 오른쪽으로 last는 왼쪽으로

first와 last가 만났을때 탐색 대상이 하나 남았다는 뜻

first와 last가 역전되면 탐색이 끝남.

★★

-1 혹은 +1을 추가하지 않으면 first <= mid <= last가 항상 성립이 되어,

탐색 대상이 존재하지 않는 경우 first와 last의 역전 현상이 발생하지 않는다.