bsearch.cpp

经典c++程序的实现

#include <iostream.h>
#include <stdlib.h>
#include "..\include\book.h"

#define UNSUCCESSFUL -1

int binary(int K, int* array, int left, int right) {
  // Return position of the element in array (if any) with value K
  int l = left-1;
  int r = right+1;     // l and r are beyond the bounds of array
  while (l+1 != r) {   // Stop when l and r meet
    int i = (l+r)/2;   // Look at middle of remaining subarray
    if (K < array[i]) r = i;     // In left half
    if (K == array[i]) return i; // Found it
    if (K > array[i]) l = i;     // In right half
  }
  return UNSUCCESSFUL; // Search value not in array
}

int main(int argc, char** argv) {
  int i, numvals, K;
  int* A;

  if (argc != 3) {
    cout << "Usage: bsearch <num_values> <search_key>\n";
    exit(-1);
  }

  numvals = atoi(argv[1]);
  K = atoi(argv[2]);

  if ((A = (int*)calloc(numvals, sizeof(int))) == NULL) {
    cout << "Error: Unable to allocate space for search array\n";
    exit(-1);
  }
  for (i=0; i<numvals; i++)
    A[i] = i;

  cout << "Binary search returns " << binary(K, A, 0, numvals-1) << "\n";
  return  0;
}