// 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;
}

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