C++ :: Binary Search Algorithm - Find Sum Of Used Number In Sequence
Mar 27, 2014
I have to made a programme which will search for given number and it must work in O(log(n)). The problem is that this programme beside finding this number have to find how many times this given number is used in this sequence.
Sequence is from lowest to highest only one possibility to use binary search algorithm
For example when we have squence
-1 -2 3 3 3 3 4 5 6 7 7 8 9 9 9 9 10
The numbers we need to search are
1 , 3 , 7 , 9 , 11 , 12
The answer is
0 , 4 , 2 , 4 , 0 , 0
So we need to find the sum of used number in sequence.
I have written algorithm Code: int start = 0;
int end = sequencelenght - 1;
int mid = 0;
/// Binary serach
while (start<=end) {
int mid=(start+end)/2;
if (sequence[mid]==givennumber) {
[Code] .....
As u see i search for given numer with binary with O(log(n)) but when i have to sum the duplicates the only good way i see is using loop to right and left but this have got log(n) specification (because when sequence would be for example 7 7 7 7 7 7 7 7 7 and given number to search will be 7 this will be O(n) loop).
How would look the most optimal algorithm look for this exercise? I mean O(log(n)) the fastest algorithm....
View 6 Replies
ADVERTISEMENT
Mar 23, 2014
i'm trying to use binary search to find a number in the array but i dont know whats wrong with my code. When l enter a number which DOES exist in the array, everything is ok... but when i enter a number which does NOT exist in the array, i have problem...i cant exit the program, it just continues to run.Here is my code
int main()
{
int FirstPosition;
[Code]....
View 2 Replies
View Related
Sep 16, 2013
Write a program to find the number of comparisons using the binary search and sequential search algorithms
//main.cpp
#include <cstdlib>
#include <iostream>
#include "orderedArrayListType.h"
using namespace std;
int main() {
cout << "." << endl;
[code]....
View 4 Replies
View Related
Oct 3, 2013
I'm trying to use the biSearch function to search for a keyword in the dictionary.
Code:
int biSearch(Dict DictEntries[MAXENTRIES],int start, int finish,char *keyword) {
int mid = (start+finish)/2;
int index = strcmp(DictEntries[mid].key,keyword);
printf("%s=%s
",DictEntries[mid].key,keyword);
[Code] ....
View 4 Replies
View Related
Nov 28, 2014
Write a program that has an array of at least 20 integers. It should call a function that uses the linear search algorithm to locate one of the values. The function should keep a count of the number of comparisons it makes until it finds the value. The program then should call a function that uses the binary search algorithm to locate the same value. It should also keep count of the number of comparisons it makes. Display these values on the screen.
/*
search benchmark.cpp
this program searchs through a array of 20 integers
*/
#include <iostream>
#include <string>
#include <iomanip>
using namespace std;
int array [20];
int count;
[Code] .....
View 1 Replies
View Related
Apr 16, 2014
I am creating a menu-driven program which creates a small database using a binary search tree. I am having issues with the last method I need for the program. The way it is coded now only gives me blank data when I print it. Here is the exact wording for the requirements for this method:
"Output a complete report to the text file named BillionaireReports.txt in increasing order by billionaire rank, that contains all data fro each record stored in the BST. Note: this is not a simple traversal. You may assume that the rank is never less than 1 and never greater that 500. Do NOT copy the data into another BST, into an array, into a linked list, or into any other type of data structure. Retrieve the data directly from the binary search tree which is stored in order by name."
Here is the method in question:
void BillionaireDatabase::displayRankReport() {
int i = 1;
for(i; i <=500; i++) {
billionaireDatabaseBST.contains(Billionaire& anItem);
[Code] ....
I know how to sort the database by the key, but I'm not sure how to sort by something that is not the key.
Here are the functions I have available via the BST (these were written by the professor)
//------------------------------------------------------------
// Constructor and Destructor Section.
//------------------------------------------------------------
BinarySearchTree();
BinarySearchTree(const ItemType& rootItem);
BinarySearchTree(const BinarySearchTree<ItemType>& tree);
virtual ~BinarySearchTree();
[Code] ....
View 3 Replies
View Related
Sep 3, 2013
Basically i need to make a number guessing game where user thinks of a numbver from 1 - 100 and the machine will try to guess it in the least number of times. Once it guesses the number it will also say how many tries it took to guess.
My code so far is
#include<iostream>
using namespace std;
const int MAX = 100;
int main() {
char ch;
cout << "Think of an integer number between 0 and " << MAX<<endl;
cout << "Write it down on a piece of paper then hit a key to continue"<<endl<<endl;
cin.get(ch);
[Code] ....
View 2 Replies
View Related
Apr 23, 2015
My assignment is "Search Benchmarks: Write a program that has a sorted array of at least 20 integers. It should call a function that uses the linear search algorithm to locate one of the values. The function should keep a count of the number of comparisons it makes until it finds the value. The program then should call a function that uses the binary search algorithm to locate the same value. It should also keep count of the number of comparisons it makes. Display these values on the screen."
I'm unsure how to make it show the number of comparisons it takes to find the value for the binarySearch function. Also, where to put the selectionSort function the teacher said we need. This is what I have...
#include <iostream>
using namespace std;
int linearSearch(const int a[], int num);
int binarySearch(const int a[], int num);
void selectionSort(int a[]);
[Code] .....
View 1 Replies
View Related
May 10, 2013
Given a set of DNA string. Find minimum length string S so that, given DNA strings are subsequence of S.
For example, if given set of string is: {CAGT, ATGC, CGTT, ACGT, AATT} then answer is: 8. Because, ACAGTGCT contains all given DNA as subsequence.
Given n such DNA string (n <= 8), each of length atmost 5. Find out the least length.
Sample:
5
AATT
CGTT
CAGT
ACGT
ATGC
Output:
8
View 2 Replies
View Related
Mar 7, 2013
I am trying to implement a Task scheduler where i have n number of tasks. The Idea behind my task scheduler is that in a loop of queues of a vector, task should get enqueued to the shortest queue among the loop of queues, which is done by the following code.
#include <vector>
#include <queue>
std::vector<std::queue<int> > q
int min_index = 0;
task t // implemented in the other part of the program
[Code] ....
Next i am trying to extend this paradigm to reduce the overhead time of the scheduler, Instead of searching the shortest queue every time, search after some condition ie. search the shortest queue after 5 tasks gets enqueued to the shortest queue.
i need to do something like this
#include <vector>
#include <queue>
std::vector<std::queue<int> > q
task t // implemented in the other part of the program
while(q[min_index].size()!=q[min_index].size()+5) // check whether current min_index queue's size is increased 5 more times if not goto enqueue
[code].....
View 1 Replies
View Related
Oct 7, 2014
inputting a search array. I tried putting a binary search but I can't get it to work. everything else works up until I put the value I am searching for in the array, then it just crashes.
How it suppose to work: input 2 coordinates with a value each then it calculates the distance between them then it suppose to let user search the coordinates for a value and state if found which coordinate it is at.
#include "stdafx.h"
#include <iostream>
#include <iomanip> //for setprecision
#include <math.h>
[Code].....
View 3 Replies
View Related
May 11, 2013
c++ program that reads in a sequence of binary digits (values 0 and 1) and stores them into a STL container. The input should terminate on any input that is not a 0 or 1. After finishing the read-process, apply a "bit-stuffing" algorithm to the container. In this case the bit stuffing should occur after four consecutive bits of the same value.i,e. four 0's or four 1's.. Also write the de-stuffing code to process the stuffed data to recreate the original data and verify that the original data is recovered correctly.
View 6 Replies
View Related
Mar 22, 2013
Any example of a graph search algorithm that uses a recursion and linked list based stacks to determine a route from a single point on a graph to another single point on a graph?
View 3 Replies
View Related
Mar 25, 2013
Any examples of a c++ program that uses recursion to find the longest increasing sequence from a grid in a file. Like
2 4 6 8
10 12 14 16
18 20 22 24
I have to use a structure named Point and a structure named Sequence.
const int MAXROWS = 4;
const int MAXCOLS = 4;
const int MAXFILENAME = 255;
// Structure used to define a point (x,y) in the grid.
typedef struct {
int x, y;
[Code] .....
View 1 Replies
View Related
Sep 16, 2013
I have to write a program to find the nth number of the Ulam numbers.
It's a bit complicated to explain what an Ulam number is but Wolfram explains it very well here: [URL]
I have to find the nth Ulam number but I don't know what I have to do to get that. My program gives me all the Ulam numbers from a range of 0 to n.
What I want the program to do is tell me that the 49th Ulam number is 243.
/*
C++ Program to find nth Ulam Number
*/
#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
int main() {
int num = 0;
vector<int> v;
[code]....
View 4 Replies
View Related
Apr 24, 2013
I am trying to write a program that checks whether the number is in sequence(as in if the numbers are in order it is a sequence). Ex: If the numbers are {1,2,3,6,7,8,9,10,11,13,15,17,20,21}, then, the underlined parts are a sequence. Now i want to find
1) the no of sequence in the array(in the above it is 3 )
2) the longest sequence (7to 11 which is 5).
View 2 Replies
View Related
Feb 16, 2014
The next code is right. I mean it works. It gives the sequence of fibonaci numbers ...
Code:
#include <iostream>
#include <iomanip>
using namespace std;
int fibo(int pos) {
if(!pos)return 0;
if(pos==1)return 1;
[Code] .....
But.... when I change the lines:
Code:
int r1=fibo(pos1);
int r2=fibo(pos2);
int r=r1+r2;
For the lines:
Code:
int r=fibo(pos1)+fibo(pos2);
It doesn't work right. Apparently it should work the same.
View 11 Replies
View Related
Nov 18, 2014
I'm saving the images in folder by using:
webClient.DownloadFile(href, sourcepath);
I don't want to give name as Current date and time..shown in given below code
string sub = @"Gadhada";
DirectoryInfo subFolder = dir1.CreateSubdirectory(sub);
Imagename = DateTime.Now.Year.ToString() + DateTime.Now.Month.ToString() +
[Code].....
I want to save my imagename as 1.jpg, 2.jpg, 3.jpg.
View 1 Replies
View Related
Feb 28, 2013
I was trying to create a code to calculate the nth number in a Fibonacci sequence, when the nth number is entered interactively.
View 4 Replies
View Related
Jun 19, 2013
I need to implement the fibonacci number sequence. Here is an example output of the program:
Server:Waiting for connection
Server:Receive connection from client
Client:10
Server:Print 10 Fibonacci
Server:1 1 2 3 5 8 13 21 34 54
Client:1 1 2 3 5 8 13 21 34 54
if Client send value of 5, the output would be 1 1 2 3 5
View 2 Replies
View Related
Jan 20, 2013
write algorith to display first n odd numbers ?
View 8 Replies
View Related
Sep 3, 2014
When ever I enter a value higher than 10, my out put looks like this
How many numbers are in the Fibonacci Series? 20
0 0 0 0 0 0
0 0 0 0 34 21
13 8 5 3 2 1
1 0
Press any key to continue . . .
This is what I got when I entered the value 20.
As you can see, it will only display up to the 10 term of the Fibonacci sequence
I'm trying to get the output to look like this:
4181 2584 1597 987 610 377
233 144 89 55 34 21
13 8 5 3 2 1
1 0
Here is my code:
#include <iostream>
#include <iomanip>
using namespace std;
#define SIZE 20
void Fibonacci( int );
int main( ) {
cout << "How many numbers are in the Fibonacci Series? ";
[code].....
View 2 Replies
View Related
Dec 8, 2014
I want to write an algorithm to find the kth term of a series given by the following recursive formula:
a_0=1 and a_(k+1)=a_k+1/k!
My code (part of it responsible for calculating the value of a series) does not want to compile:
Code:
float series(int n)
{
float F0 = 1;
float F;
unsigned int i;
if (n == 0)
return(1);
[Code]...
thus my question is why it does not want to work properly and what should i change (for certain factorial function is OK)?
View 7 Replies
View Related
Dec 9, 2014
I was doing a side project from my textbook about finding the mode, which is the number that occurs most often in a sequence of numbers. I racked my brain on this for an embarrassing amount of time and finally came up with this, which I think works but for some reason I still feel like I'm not done.
#include "stdafx.h"
#include <iostream>
using namespace std;
void mode(int *, int);
void main() {
const int NUMBERS = 15;
int list[NUMBERS] = {99,73,56,14,28,42,93,64,51,26,56,16,38,81,98};
mode(list,NUMBERS);
[Code] ....
Console Output:
Final Mode 56
Press any key to continue . . .
There it is, I would have commented more but I couldnt think of the right words to explain everything.
View 4 Replies
View Related
Mar 24, 2014
write a program in c to read a sequence of N integers and print the number that appears the maximum number of times in the sequence.
View 1 Replies
View Related
Feb 6, 2014
In this program what i'm doing is to search for a number when the vector is in order, and count how many times that number appears, the problem is that count how many times the number does not appear, but when its appear the program stays in an "standby mode" and the cursor does not move.
int buscarNumOrdenado (int x [MAX]) //MAX is the define {
int num,d, LimiteInferior, LimiteSuperior,mitad;
d=0;
LimiteInferior = 0;
LimiteSuperior = MAX-1;
[Code] ....
View 2 Replies
View Related
