2분 찾기 및 확장

질서수 그룹에서 이분 검색은 효율이 비교적 높은 검색 알고리즘이다.이분 검색에는 일반적으로 귀속과 교체가 있다

// 
int binarySearch(int *data, int target, int start, int end){
    if(start > end)  return -1;
    int midIndex = (start + end) / 2;
    int midData = data[midIndex];
    if(midData == target)
          return midIndex;
    else if(midData > target)
         end = midIndex - 1;
     else 
         start = midIndex + 1;
    return binarySearch(data,target,start,end);
}
// 
int binarySearch(int *data, int target, int length){
     int low = 0, up = length; 
      while(low < up){
           int midIndex = (low + up) / 2;
           int midData = data[midIndex];
           if(midData == target)   return midIndex;
           else if(midData > target)  up = midIndex - 1;
           else  low = midIndex + 1;      
    }
  return  -1;
}

질서정연한 수조에서 지정한 숫자가 수조에 나타난 횟수//이분 검색을 통해 지정한 숫자가 나타난 첫 번째와 마지막 숫자의 위치를 알면 출현 횟수를 확정할 수 있다.

// 
        while(low < up){
            size_t mid = (low + up) / 2;
            int middata = data[mid];
            if(target < middata )
                up = mid;
            else if(target > midata)
                low = mid;
            else if(target == middata){
                if((mid > 0 && data[mid-1] != target) || mid == 0 )
                   return mid;
                else
                    up = mid -1;
            }
        }
        
// 
        while(low < up){
            size_t mid = (low + up) / 2;
            int middata = data[mid];
            if(target < middata )
                up = mid;
            else if(target > midata)
                low = mid;
            else if(target == middata){
                if((mid < length-1 && data[mid+1] != target) || mid == length -1 )
                   return mid;
                else
                    low = mid -1;
            }
        }

질서정연한 수조에 대해 이 수를 수용할 수 있는 위치를 찾아라//2분 검색을 통해 현재 수보다 작지만 이전 수보다 큰 위치를 찾아라

        while(low < up){
            size_t mid = (low + up) / 2;
            if(target < core[mid] ){
                if(target > core[mid - 1]){
                    j = mid;
                    break;
                } else if(target < core[mid - 1]) {
                    up = mid;
                } else if(target == core[mid - 1]) {
                    j = mid-1;
                    break;
                }
            } else if(target > core[mid]){
                low = mid;
            } else if(target == core[mid]){
                j = mid;
                break;
            }
        }
        cout << j << endl;