搜索排序数组中的元素

#1 楼

#include <iostream>
#include <algorithm>

using namespace std;

// This function signature is required:
int get_num_of_ints(const int* searchBegin, size_t searchSize, int input,
    size_t* first, size_t* count) {
  const int* searchEnd = searchBegin + searchSize;
  const int* result = lower_bound(searchBegin, searchEnd, input);

  if (searchEnd == result || *result != input)
    return -1;

  *first = result - searchBegin;
  *count = upper_bound(result, searchEnd, input) - result;
  return 0;
}

void print_search_results(const int* searchBegin, size_t searchSize, int input) {
  size_t first;
  size_t count; 

  if (get_num_of_ints(searchBegin, searchSize, input, &first, &count) < 0) {
    cout << input << " is not in the array." << endl;
    return;
  }

  cout << input << " was found at index " << first << ". "
       << "There are " << count << " instances for " << input << " in the array."
       << endl;
}

bool read_input(int* input) {
  cout << "Enter a number to search for: ";
  bool succeeded = cin >> *input;
  cout << endl;    
  return succeeded;
}

int main (int argc, char** argv) {
  const int searchNumbers[] = {1, 2, 4, 4, 5, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 11, 13};
  const int searchNumbersSize = sizeof(searchNumbers)/sizeof(searchNumbers[0]);

  while(1) {
     int input;
     if(!read_input(&input)) {
       count << "Bad input, exiting" << endl;
       return 1;
     }

     print_search_results(searchNumbers, searchNumbersSize, input);
  }
}

#2 楼

if (condition)
    consequence;
statementx;
...

if (condition)
    consequence1;
    consequence2;
statementx;
...

#3 楼

m = (hi + lo)/2;

m = lo + (hi - lo) / 2;

m=m;

#4 楼

#5 楼

#6 楼

#7 楼

#include <stdio.h>

int binary_search( const int value, const int *arr, size_t start, size_t end ){
    if( value < arr[start] || value > arr[end] ){
        return -1;
    }

    while(start <= end){
        int pivot = (start+end) >> 1; 
        if(arr[pivot] == value){
            return pivot;
        }else if(arr[pivot] < value){
            start = pivot+1;
        } else if(arr[pivot] > value){
            end = pivot-1;
        } 
    }
    return -1;
}

int get_occurences( int begin, const int *arr, size_t max){
    int counter = 1;
    int cursor = begin;
    while ( (cursor+1) < max && arr[cursor] == arr[cursor+1]) {
        counter++;
        cursor++;
    }
    cursor = begin;
    while ( (cursor-1) > 0 && arr[cursor] == arr[cursor-1]) {
        counter++;
        cursor--;
    }
    return counter;
}


#define MAX 22
int main()
{   
    int value;
    int arr_sorted []={1,1,2,3,3,
                       4,4,4,4,5,
                       5,7,7,7,7,
                       8,8,8,9,11,
                       12,12};    
    size_t arr_size = MAX; // works also the other way               

    printf( "\nPlease input the integer you would like to find.\n" );
    scanf( "%d", &value );
    printf("Searching %d\n", value);
    int pos = binary_search( value, arr_sorted, 0, arr_size-1);

    if( pos == -1) {    
        printf( "%d has not been found.\n", value );
    } else{
        int howmany = get_occurences( pos, arr_sorted, arr_size);
        printf( "The first matching index is %d.\n", pos );
        printf( "The total number of instances is %d.\n", howmany );
    }

    return 0;
}

#8 楼

#9 楼

#10 楼

#11 楼

// returns the number of matches, and sets pos to the index of
// the first match, or -1 if none found
int findMatches(int array[], int size, int searchNum, int* pos)
{
   *pos = binarySearch(array, size, searchNum, -1);
   // if it was found, pos points to a positive number
   if(*pos >= 0)
   {
      int lastIdx = binarySearch(array, size, searchNum, 1);
      return lastIdx - *pos + 1;
   }
   return 0;
}

int binarySearch(int array[], int size, int searchNum, int direction)
{
   int left = 0;
   int right = size - 1;
   int center;
   int pos = -1;

   while(left <= right)
   {
      center = (right + left) >> 1;

      if(array[center] == searchNum)
      {
         pos = center;
         // break early if we want to find the exact match
         if(direction == 0) break;
      }

      // adding 1 to searchNum means we will find the last in the run
      if(array[center] < searchNum + ((direction > 0) ? 1 : 0))
      {
         left = center + 1;
      }
      else
      {
      　  right = center - 1;
      }
   }

   return pos;
}

#12 楼

#13 楼

#14 楼

#15 楼

#16 楼

if( a < 0)    
    printf( "%d has not been found.\n", N );
else //if(a >= 0)
{ ...


if(arr[m] < N)
    lo = m+1;
else if(arr[m] > N)
    hi = m-1;
else //if(arr[m]==N)
{ ...

    if( j > 0 && L > 0 )
        *first=j+1;
    else if( j==0 && L==0)
        *first=m;
    else if( j > 0 && L==0 )
        *first=m;
    else if(j < 0 && L==0 )
        *first=m; 
    else if( j < 0 && L > 0 )
        *first=0;
    else //if( j=0 && L > 0 )
        *first=j+1;

#17 楼

#include <stdio.h>

static const int* upper_bound(const int* begin,
                              const int* end,
                              const int value)
{
    size_t count;
    size_t step;
    const int* iter;
    count = end - begin;

    while (count > 0)
    {
        iter = begin + (step = (count >> 1));

        if (*iter <= value)
        {
            begin = iter + 1;
            count -= step + 1;
        }
        else
        {
            count = step;
        }
    }

    return begin;
}

static const int* lower_bound(const int* begin,
                              const int* end,
                              const int value)
{
    size_t count;
    size_t step;
    const int* iter;
    count = end - begin;

    while (count > 0)
    {
        iter = begin + (step = (count >> 1));

        if (*iter < value) /* upper_bound compares "*iter <= value" */
        {
            begin = iter + 1;
            count -= step + 1;
        }
        else
        {
            count = step;
        }
    }

    return begin;
}

void get_number_of_ints(const int* array,
                       size_t array_length,
                       int target_value,
                       size_t* first_index,
                       size_t* count)
{
    const int* iter1;
    const int* iter2;

    iter1 = lower_bound(array, array + array_length, target_value);

    if (*iter1 != target_value)
    {
        /* No match. */
        *count = 0;
        return;
    }

    iter2 = upper_bound(array, array + array_length, target_value);
    *first_index = (size_t)(iter1 - array);
    *count = (size_t)(iter2 - iter1);
}

int main()
{
    int N;                                 /* input variable */
    int arr[]={1,1,2,3,3,4,4,4,4,5,5,7,7,7,7,8,8,8,9,11,12,12}; /* sorted */
    size_t r = sizeof(arr)/sizeof(arr[0]); /* right bound */
    size_t first;                          /* first match index */
    size_t count;                          /* total number of matches */

    /* prompts the user to enter input */

    printf( "\nPlease input the integer you would like to find.\n" );
    scanf( "%d", &N );

    get_number_of_ints(arr, r, N, &first, &count);

    if (count == 0)
    {
        printf("%d not found!\n", N);
    }
    else
    {
        printf("%d found at %zu, length %zu.\n", N, first, count);
    }

    return 0;
}

#18 楼