C++ :: Binary Searching By A Key Containing Two Variables?

Nov 24, 2014

So I have an array of distinct pairs of natural numbers. That is, my array looks something like this (for instance):

{ (1,5) , (6,4), (5,3), (2,3), (2,4) }

And my task is, for a given pair (a,b) find (if it exists) the pair (c,d) which has c > a and d > b and, in addition, is the "minimal" such pair (that is, c is minimal and, if there are multiple pairs which satisfy this with the same c, then d is minimal.

So for instance, if I run the query for the above array for pair (1,1), it should return (2,3) and if I feed it (5,2) it should return (6,4).

Now the problem is that I have to run multiple queries so linear time is not good enough. And my question is: is there any way in / any law by which I can "sort" such an array so that I can later run binary searches on it to find my answer?

I was thinking I could simply go like this: let (x1,y1) and (x2,y2) be two pairs to compare. Then:

if(x1<x2)
//pair 1 is smaller
else if(x1==x2 && y1<y2)
//pair 1 is smaller
else
//pair 2 is smaller

This seemed to solve most cases, however.. if I have an array which looks like this:

{ .... (50,60) ..... }

where (50, 60) is at the middle of the array. And I run a query for (40,70) for instance. The problem is that the pair that I want to find could be either on the left or on the right of (50,60) (we could have something like (45,90) on the right of (50, 60), but then again we could only have (x,10) on the left of (50,60) where x<50 so no pair on the left would satisfy our condition and I'd have to look to the right).

So to sum it up, if I'm running a query for pair (x1,y1) and through my binary search I come across and element (x2,y2) which has x1<x2 and y1>=y2, then my algorithm cannot decide whether it should keep searching left or right. So I have to search both sides and in a worst case scenario this ends up being O(n).

View 7 Replies


ADVERTISEMENT

C/C++ :: Searching A Binary Tree?

Mar 1, 2015

I've almost got my code working. My issue is, if I type in either one of the first two id numbers, it finds the person and displays as it's supposed to, however if I type any of the last 6 id numbers it says id not found. I've been staring at this forever and can't see what I'm missing />/> ps, I haven't added in all my comments yet Binary tree template

//Binray tree template class
#ifndef BINARYTREE_H
#define BINARYTREE_H

[Code].....

View 14 Replies View Related

C++ :: Searching By Last Name?

Oct 23, 2013

I have an assignment to create an address book in c++ where you can enter contact information and then search all entries via last name. I am trouble figuring out how to write a function that will be able to search an entry by last name. Here is my code so far:

#include <iostream>
using namespace::std;
class addBook {

[Code]....

View 1 Replies View Related

C++ :: Searching In CSV File?

Feb 6, 2013

My .csv file is like:

Bone,origin,deep/superficial,location, action.

with list of 38 bones.

This is my main.cpp:

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <cstdlib>
#include "Action.h"
#include "Action.cpp"

[Code] .....

For action, if user enters action, it will output the bones involved with that action.
For strengthening, if user enters location, it will output bones involved with that location.
For dagnostic, if user enters bone, it will output location of bone and whether bone is deep/superficial.

How I could search in csv file for these.

View 11 Replies View Related

C# :: Searching DB For Value In Textbox (WPF)

Nov 3, 2014

WPF window I'm working on. I have a window that has a textbox to enter a name to search a database table for, and when the search button is clicked, the ID for that username will be returned to a separate textbox. The code I've written atm doesn't seem to be working, but it looks fine to me. Here's what I've got;

private void btn_SearchUsers_Click(object sender, RoutedEventArgs e)
{
if (!string.IsNullOrWhiteSpace(txtb_SearchName.Text))
{
SqlConnection sqlCon = new SqlConnection(conStr);

[Code] .....

So, I have the value entered into the textbox to be searched for stored in a variable, I'm selecting the ID from the table when the name in the variable is found, storing the result in a DataTable, and then in my foreach loop, if I find the name (the name column being index 1 in the table), I set set the ID result textbox to equal the ID for that name (the ID column being index 0 in the table). I think the foreach part is what's throwing me off. Maybe the column stuff? My Users table is like;

ID Name
1 John
2 Roger
3 Mike

View 3 Replies View Related

C :: Searching Word Using Strcmp

Nov 15, 2014

I'm trying to write function that finds wheter the searched word exists or not. The compiler gives warning. Where is my wrong ?

|21|warning: passing argument 1 of 'strcmp' makes pointer from integer without a cast [enabled by default]|

Code:

#include <stdio.h>
#include <string.h>
int main ()
{
int result;
char arr[]="sakir emmim evde mi evde mi dedik lan";
int size=sizeof(arr)/sizeof(char);
char key[20];
scanf("%s", &key);

[Code]...

View 6 Replies View Related

C++ :: Functions Searching A Database

Aug 8, 2013

I am trying to write a program to search a library file with the name of a book or author and return the books that match the searched string in some way. For instance, if I search "Develop" it should display Game Development Essentials(Novak) and Developing Games in Java(Brackeen) and tell me that 2 records were found. Currently, it shows all the records regardless of what i search for, even if it is jibberish. Am I missing something in my functions? should I include the code that accesses these functions?

//If the user chooses A or a
int showBooksByAuthor (int count, string name)
{
char choice;
int index = 0;
}

[code]....

View 1 Replies View Related

C++ :: Searching For Line Intersections

Jul 26, 2013

I'm pretty decent at maths, and fair at programming but how I'd actually write mathematical line equations or check for intersections in script.

View 5 Replies View Related

C++ :: Searching A MultiMap With Regex

Apr 24, 2014

I have a multimap with over 300k entries defined like so: std::multimap<std::string, std::string> filedata;

Using the following code and std::multimap::equal_range, I am able to successfully search for a word in the multimap and get needed data:

// Data with strings.
data = std::vector<std::string>();
// Get iterators to matched pairs.
std::pair <std::multimap<std::string, std::string>::iterator, std::multimap<std::string, std::string>::iterator> dat = filedata.equal_range(word);
// Go through each matched pair and get needed info.
for (std::multimap<std::string, std::string>::iterator iter = dat.first; iter != dat.second; iter++) {
data.push_back(iter->second);
}

Now, I would like to search the multimap using regular expressions (EX: std::regex("[a-z][a-e]h")). What is the fastest way to do this? Example code may look like:

std::pair <std::multimap<std::string, std::string>::iterator, std::multimap<std::string, std::string>::iterator> dat = filedata.equal_range_with_regex(std::regex("" + word + ""));. Pseudo-code / algorithms will be enough.

View 2 Replies View Related

C++ :: Searching Files For A String

Jan 30, 2013

I have 80,675 Files, 8,213 SubFolders.

I would like to search each file for a string, which will be last name.

Matches string, outputs path/filename, either to screen or a output file.

I have done this to a single file but never to multiple files and folders.

View 2 Replies View Related

C++ :: Searching / Reading CSV File

Jan 29, 2014

How do i search a csv file?. I have a table with 3 columns (Employee ID , salary ,grade ) If i will enter an Employee ID and it should return the salary and grade of that employee id.

View 2 Replies View Related

C++ :: Searching An Ordered List

Oct 3, 2013

Make an ordered array. Put a bunch of random numbers into it. Do 20 linear searches and 20 binary searches of that array. (Code for linear search and binary search are found in the book.)Print out how many elements were checked before the item is found

I'm not looking for answers as it is homework. However I don't understand what I'm doing. This course is being held online(no other options) and that's not how I learn so I'm struggling. From my understanding I have to make a templated ordered array (which I don't understand at all) and then do searches (which I also don't understand).

View 1 Replies View Related

C++ :: Searching A Text File?

Apr 23, 2013

im trying to make a function that will take in a users ID and search a text file for that ID and if there is a match to print out the matched line and the following 3 lines that follow. so far i ahve the following code but i cant get that to work and i dont knwo how to do the rest.

//declaring a file variable
FILE *fpcust;
int line_num = 1;

[Code].....

View 3 Replies View Related

C++ :: Searching Vector With Maps?

Sep 19, 2014

Currently im creating a simple phone directory. I am having a problem when searching the vector. It only lets me search for the exact key in the directory when I need to to search for strings that are close to the name. For example when I search "car" it will state that its not in the directory when it should pull up Carr, Derek and Carr David.

#include <string>
#include <map>
#include <vector>
#include <ostream>
#include <iostream>
int main() {
std::map<std::string, std::vector <std::string> > directory;

[code]....

View 1 Replies View Related

C++ :: Searching For Character In String

Jun 19, 2013

I'm trying to find a < character in a document, get it's position. Then find > and get it's position. Then i want to delete all things between that but runtime is terminating my process so i don't know what to do.

The code:

#include <iostream>
#include <conio.h>
#include <stdio.h>

[Code].....

View 6 Replies View Related

C++ :: Searching A List Of Vectors?

Apr 30, 2013

How would you search through the a list of vectors? I have a upper case letter at the start of the lists and corresponding lower case letters in vectors how would I search through it to see how many times the corresponding lower case letter was repeated?

View 1 Replies View Related

C++ :: Searching A Number In Int Array?

Oct 12, 2013

Basically I initialize an int array of size 10 with zeros. Then element 7 is changed to 1. Via cin I collect a user input (integer) which is the number to be searched.

Now the problem is that the search function from the book is somehow not working. I added a function to see how the array looks like and there is definitely one element with value 1 that should be found, but it simply isn't. The function always returns -1 (element not found).

The program compiles, but doesn't work as it is supposed to.

//********************************************************
// search algorithm for arrays
//********************************************************
#include <iostream>
using namespace std;

[Code].....

View 5 Replies View Related

C++ :: Searching For Errors Within A Code

Dec 17, 2014

i use cygwin and i have a program that was returning an error saying "undefined reference" and i figured out that i misspelled a word. how can i search for the misspelling in the input mode, if ive just completed a very large program and dont want to scroll through possibly 300+ lines of input? im not totally out the loop, but i know i can "vim program.cpp" to open the program, but before clicking "i" to actually edit, there must be a way to search a word

View 9 Replies View Related

C/C++ :: Sorting 10 Names And Searching For One

Mar 5, 2015

So I been asked to write a program that does the following:

Write a program that allows the user to enter a series of 10 names from the keyboard and then sorts and prints the names in alphabetical order. Use a series of functions:

1) Input the data
2) Sort the data (use a bubble sort)
3) Print the data

After this is done, allow the user to enter a name from the keyboard and determine if the name appears in the list. Use a function to accomplish the search. The name to be searched for should be input within main and sent to the function as an argument.

4) Search the data (use a binary search of type bool)"

this is whats I wrote so far and its giving me error with the sorting and the searching, I need to fix it and I cannot figure out how?!.

#include <iostream>
#include <conio.h>
#include <string>
using namespace std;
void bubbleSort(string[], int);
int main()

[Code]....

View 3 Replies View Related

C++ :: Searching String Within Vector Struct

Nov 3, 2013

New to C++ lambda, got two question in regards of searching for strings within a vector struct.

Minimalistic example:
Code:
struct singleFile {
std::string filename;
};

std::vector<singleFile>myStorage;
myStorage.push_back(singleFile());

[Code] ....

1) why does found always return 0 eventhough the filename exists?

2) I don't know how to pass an actual search string instead of the hardcoded approach as above with filename =="

View 6 Replies View Related

C++ :: Searching Char By Diagonal Not Only The Main

Mar 6, 2015

I have a problem with searching chars by diagonal not only the main, i have a chars in vector and I need to go though all possibilities (as shown in picture) the word has to be side/2 long so here i have 9, so word has to be 4 chars long how I need to do this?

View 2 Replies View Related

C :: Searching Array Of Struct Students

Feb 28, 2013

I have to search an array of struct students on the basis of their first names, last names and roll numbers .. so far i am done with the input of the student first , last names and roll numbers . I have problem in searching the array ..

Code:
#include <iostream> Code: #include <string>
using namespace std;
struct Student {
string FirstName ;
string LastName ;

[Code] ....

View 5 Replies View Related

C :: Searching A String On Char Matrix

Apr 12, 2014

I want to make a program that receives the number of lines and collumns of a matrix, a matrix of char, the number of pairs of coordinates and the coordinates. the program has to return the char (or chars) that are on those coordinates on the matrix.

Example:

receives
2 3 ABC DEF 2 1 1 1 2

returns

AB

this is how i tried to solve this problem:

Code:
#include
#define MAX 1000
int main() {
int nlin, ncol;
char mat[MAX][MAX];
int x[MAX], y[MAX];
int ncoords;
int l, c, n;

/* receiving variables and storing matrix.*/

[Code] .....

For some reason that i can't seem to find, this solution is not right.

View 6 Replies View Related

C++ :: Searching For A Container With Multiple Keys

Apr 7, 2013

I need a container which has multiple keys. The number of keys, which are related to a value, is not constant, but it is small. (less than 10). I have tried to do this with std::map, but things are working only with a constant number of keys per value.

Something like this

key1 ----|
key2 ----|--------- value1
key3 ----|

key4 ----|--------- value2
key5 ----|

View 11 Replies View Related

C++ :: Searching For Email Format And Domain

Feb 26, 2015

I am new to C++ and programming in general. I was wondering if it is possible to use C++ to search for company email formats and domain addresses?

For example, finding the correct format like:

jsmith@carnival.com
or
johnsmith@carnival.com
or
j.smith@carnival.com

Also, if it is possible to find the actual email domain, such as:

@carnival.com
or
@carnivalcruises.com
or
@carnivalcorp.com

View 4 Replies View Related

C++ :: Searching For Objects In Linked Lists

Jun 18, 2013

So I have a Class named Subject, wich I used linked list to keep the objects. Now I have another Class called Tests which I should register a test by the Subject class, so I made a search like this:

List obj; //it's the object to access the List class, which manipulates the
//nodes from Subject.

obj.currentPtr=obj.firstPtr;
while (obj.currentPtr!=NULL) {
if(obj.currentPtr->nameSubject==value) //searching if there's a
return obj.currentPtr; //name equal to provided
obj.currentPtr=obj.currentPtr->nextPtr;
}
return 0;

I've made a similar process for Subject. But in this when I access the firstPtr, it's shown to be 0, once I have already the list of Subject and it should not be zero. What's wrong?

View 3 Replies View Related







Copyrights 2005-15 www.BigResource.com, All rights reserved