二分查找及其扩展

在有序数组中，二分查找是效率较高的查找算法。
二分查找一般有递归和迭代

//递归版本
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;
            }
        }

对有序的数组，找到正好可以容纳这个数的位置
//通过二分查找，找到正好小于等于当前数，却大于前一个数的位置

        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;