Differences

This shows you the differences between two versions of the page.

Link to this comparison view

mergesortedlist.cpp [2014/10/26 01:52] (current)
Line 1: Line 1:
 +<​code>​
 +// FindPosition.cpp
  
 +// Write a function that performs a binary search on an array of integers.  ​
 +// Function prototype given below. ​ You may not call any C library functions.
 +
 +//    int FindPosition(const int * rgNumbers, const size_t cNumbers, const int nToFind);
 +
 +//    Sample input: ​ [-87 -12 33 122 40928], 5, 33
 +
 +//    Sample output: ​ 2
 +
 +// assumptions : binary search can be performed on a sorted array of ints
 +// I will assume that the array is sorted. if not sorted then this method will fail
 +// will return -1 if number not found in array else will return the array index of the number
 +
 +// ===== include'​s =====
 +#include <​iostream>​
 +#include <​stdio.h>​
 +
 +#include "​FindPosition.h"​
 +
 +using namespace std;
 +
 +// ===== define'​s =====
 +#define DEBUG 0
 +// ===== globals =====
 +
 +// ===== function prototypes =====
 +
 +// ===== FindPosition() =====
 +int FindPosition(const int * rgNumbers, const size_t cNumbers, const int nToFind) {
 + if (cNumbers == 0) return -1; // array is empty
 + if (cNumbers == 1) {
 + if (nToFind == rgNumbers[0])
 + return 0;
 + else ​
 + return -1;
 + }
 +
 + int upperBound=0,​ lowerBound = 0, position = 0;
 + upperBound = cNumbers;
 + position = (upperBound + lowerBound) / 2;
 + bool found = false;
 +
 + while (!found && (lowerBound < upperBound)) {
 +#if DEBUG == 1
 + cout << "pos : " ​
 + << position
 + << " "
 + << rgNumbers[position] ​
 + << " low : "
 + << lowerBound
 + << " upp : " ​
 + << upperBound
 + << endl;
 +#endif
 + if (nToFind < rgNumbers[position] ) {
 + upperBound = position-1;
 + } else 
 + if (nToFind > rgNumbers[position]) {
 + lowerBound = position+1;
 + } else 
 + if (nToFind == rgNumbers[position]) {
 + found = true;
 + }
 + if (!found) position = (upperBound + lowerBound) / 2;
 + }
 + if (found)
 + return position;
 + else
 + return -1;
 +}
 +
 +</​code>​
 +
 +----
 +  * [[cplusplus|Back to C++]]
mergesortedlist.cpp.txt ยท Last modified: 2014/10/26 01:52 (external edit)
CC Attribution-Share Alike 3.0 Unported
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0