Questions tagged [search]
This tag is for questions about search algorithms, tools, and technologies.
382
questions
155
votes
20
answers
32k
views
Searching an element in a sorted array
I was applying for a position, and they asked me to complete a coding problem for them. I did so and submitted it, but I later found out I was rejected from the position. Anyways, I have an eclectic ...
Micky
51
votes
12
answers
22k
views
Searching in an array in less than O(n) time
I have an array where each element is either one less or one greater than the preceding element \$\{x_i = x_{i-1} \pm 1\}\$. I wish to find an element in it in less than \$O(n)\$ time. I've ...
- 698
39
votes
5
answers
7k
views
JavaScript binary search
I wrote an implementation of binary search in JavaScript earlier for kicks, but I noticed my version was significantly different than those found on Google. Here is an example of binary search I found ...
- 493
35
votes
10
answers
9k
views
Search for a multiword string in a list of strings
Unlike Perl, you can't to my knowledge match a regular expression inside an if statement in Python and assign the result to a variable at the same moment. This ...
- 465
32
votes
4
answers
78k
views
A* search algorithm
NodeData stores all information of the node needed by the AStar
algorithm. This information includes the value of ...
- 8,391
30
votes
8
answers
50k
views
Find all the missing number(s)
Recently I've attended an interview, where I faced the below question:
Question: "There is an sorted array. You need to find all the missing numbers. Write the complete code, without using any ...
- 789
29
votes
5
answers
12k
views
Custom indexOf() without String methods
I created my own indexOf function. I was wondering if anyone could help me come up with a way to make it more efficient. I am practicing for interviews so the catch ...
- 1,499
26
votes
6
answers
213k
views
Fast way of searching for a string in a text file
I have written this code to search for a string in a .txt file. Is it possible to optimize the code so that it searches for the string in fastest manner possible? ...
- 261
20
votes
2
answers
3k
views
Search a big (13 GB) Outlook PST file
I have an Outlook PST file of a pretty big size (13 GB). For some indexing purpose I needed to scan through the full PST file to get all the PR_SEARCH_KEY and then ...
- 311
19
votes
4
answers
1k
views
Name Filtering using a Trie
This question suggests a different (improved?) implementation for searching/filtering names based on a search query. This is based on the question here: Name filtering in Java
A Trie allows the ...
- 97.3k
17
votes
7
answers
143k
views
Finding repeating numbers in an array
I want to search through an array of n numbers and find the numbers that are repeated. So far I have this code, which does the job, but I find it to be a rather cumbersome method, but I can't seem to ...
- 273
15
votes
2
answers
370
views
Hmm, a thoughtful library
I've been writing far too many routines in JavaScript that get a record from a an object or array based off a matching property, much like jQuery does with DOM elements. Since all the good names are ...
- 32.9k
14
votes
4
answers
460
views
Finding subtuple in larger collection?
I've got a flat array of < 1000 items and I need to find the indices of a smaller tuple/array within the array. The tuple to find can be a varying length (generally between 2 and 5 items, order is ...
- 243
14
votes
2
answers
2k
views
A* search in MATLAB
I have implemented A* search in MATLAB, but I am looking for ways to increase the speed and optimize it. I have tried using a priority queue but I found it doesn't work that well, so I am using a ...
- 313
13
votes
4
answers
10k
views
Find byte[] in byte[] with Java
I made a search method because I want to use binary data like PNG files. The point of this is to be able to find strings like IEND in a PNG file. I think it works ...
- 655
12
votes
4
answers
8k
views
strstr() implementation
In this strstr implementation, I am basically skipping the already matched and checked characters with an if else condition. Is ...
12
votes
5
answers
2k
views
Find all words that satisfy unknown letters (Hangman)
I have been working on a function which might be used to solve a word game like Hangman or "Wheel of Fortune".
Basically, I wish to search from a very large ...
- 241
12
votes
5
answers
9k
views
Fastest way of removing a substring from a string
Taking a break from my C++ series, I recently reviewed the code in this question. I ended up writing my own separate derivation of the function so that I could remove all of the substrings from a ...
- 21.8k
12
votes
3
answers
13k
views
Suffix tree implementation in Java
I was trying to solve the problem where given a larger string and an array/list of smaller string, we need to make the determination whether the larger string contains each of the smaller strings. I ...
- 1,213
12
votes
2
answers
609
views
Finding a word within a pre-defined set using a search string with wildcards
The other day I was intrigued by this question (originally from here):
Write a program that answers YES/NO search queries containing * placeholders. Example: if the data you have is (hazem, ahmed,...
- 111k
12
votes
1
answer
162
views
To read a book thou should have it bought, to buy a book thou should have it found! (Search Abstraction)
I started a hobby project to find the books that I read (paperbacks) so that I can keep track of them (reading start date, finish date, number of pages, etc..)
The first challenge was to find the ...
- 853
11
votes
2
answers
20k
views
Powershell search millions of files as fast as possible
I once asked a similar question but in C#. Now I have the same problem in powershell..
What is the fastest way, to search files newer than 15 minutes, in a file system with more than 1 million files?
...
- 245
11
votes
1
answer
4k
views
Z-Algorithm for pattern matching in strings
I was trying to refactor the following Python code (keeping the same time-complexity) which is an implementation of Z-Algorithm for pattern matching in strings.
...
- 221
11
votes
2
answers
1k
views
Finding an element in multiple sorted lists efficiently
I have \$k\$ sorted Lists, each of size \$n\$. Currently I have hard-coded 5 sorted Lists each of size 3, but in general that is ...
- 1,647
11
votes
2
answers
13k
views
Searching a Word Document from Excel
Today I created a script in Excel that migrates data from a specific Word document and copies a portion of it to a cell in Excel (the date to be specific).
The file input is
Last name, First Name, ...
- 357
11
votes
1
answer
1k
views
Case-insensitive String search in Array
Wrote this function for a Stack Overflow answer. It started off pretty bad but in the end I polished it a bit and now I have something I think to be pretty clean. Actually, when I look at the code, ...
- 22.3k
11
votes
2
answers
172
views
"Vc" as in Vancouver, or Valencia?
It is common to shorten city names when writing, or at least in Sweden.
"Göteborg" (Gothenburg) is often referred to as "Gbg"
"Uddevalla" is commonly written as "Ua"
"Trollhättan" is often written as ...
- 59k
11
votes
1
answer
1k
views
Karp-Rabin with bitwise hash
As a Rags-to-Riches re-implementation of the Karp-Rabin question here, from @tsleyson, I thought it would be interesting to understand the algorithm better, and to use bitwise-shifting instead of ...
- 97.3k
10
votes
3
answers
596
views
Read file with over 300k words and filter through appropriate filter to return list of matching words
As a puzzle we were asked to bring out the possibilities in breaking a 4 letter wordlock combination. It was to be a four letter word from the English dictionary. There were 10 possible characters in ...
- 203
10
votes
4
answers
301
views
Let's play Find that File
Isn't it annoying when you can't find a file you recently created? Especially when you either have a very disorganized drive or a directory with lots of files.
Even if you don't care, isn't it nice ...
- 9,454
10
votes
2
answers
584
views
Minimum sub-array challenge
Below is my solution to finding the minimum product sub-interval. It passed 8/12 or so test cases, but the other test cases timed out if they hadn't finished within 2 seconds. When I compile this code ...
- 103
10
votes
1
answer
480
views
Bash command helper in C
Previously, I had written this program in C++ and asked about it here on Code Review. After spending some time with C++, I desired to become more familiar with its namesake. This is my first C program....
- 1,350
10
votes
1
answer
1k
views
Scanning multiple huge files in Python
I'm trying to implement an algorithm able to search for multiple keys through ten huge files in Python (16 million of rows each one). I've got a sorted file with 62 million of keys, and I'm trying to ...
- 233
10
votes
2
answers
495
views
Naive implementation of KMP algorithm
After reading this answer to the question "High execution time to count overlapping substrings", I decided to implement the suggested Knuth-Morris-Pratt (KMP) algorithm. I used the pseudo-code listed ...
- 40.8k
10
votes
1
answer
1k
views
Generic domain independent Monte Carlo Tree Search methods library
I've written this small generic library for the purpose of my Bachelor's thesis. It's fully functional and unit tested and I want to get as many opinions as possible regarding overall code quality (...
- 195
10
votes
1
answer
554
views
Javascript/Typescript anagram String search
I've created a random word generator which allows me to create random words/anagrams.
Then I've created Anagram search app to find the angarams when user start typing in inbox.
Could you review ...
- 278
10
votes
1
answer
368
views
Fuzzy grep for fuzzy bears in pure Python
I am aware of the Python modules galore to do this, but this was partially a learning experience and partially all the functionality I need and no more.
I'm writing a simple interpreter for a Forth-...
- 977
10
votes
1
answer
178
views
Speed up my search
I have a django app with search powered by haystack. The general search goes very quickly, but I need to filter the results by their model type. It works but is very slow. I've never really worked ...
- 875
9
votes
5
answers
3k
views
Efficient pathfinding without heuristics?
Part of my program is a variable-sized set of Star Systems randomly linked by Warp Points. I have an A* algorithm working rather well in the grid, but the random warp point links mean that even though ...
- 253
9
votes
3
answers
21k
views
Get values between two dates
I have a search form where users can enter ValidFrom and ValidTo dates,
There are three conditions:
...
- 277
9
votes
4
answers
247
views
Stream text scanning
I've written some utilities to read text from streams. One of these, the ReadTo method, is to read text from a specified stream until a given text is encountered, ...
user168452
9
votes
2
answers
3k
views
Calculating the fastest strategy in OGame
For a game I am playing, OGame, I am trying to calculate the fastest strategy to reach a certain state in the game, relevant parts of the game for this question are:
You can build different types of ...
- 10.6k
9
votes
3
answers
4k
views
Extracting elements from multiple sorted lists efficiently
I was asked this interview question recently. I was able to come up with this which runs in \$O(k \log n)\$.
Given k <= n sorted arrays each of size n, there exists a data structure requiring \$...
- 1,647
9
votes
2
answers
1k
views
Exponential search
I recently discovered the exponential search algorithm which can be used to find whether a value exists in an ordered range. An exponential search checks whether a value is smaller than the \$2^n\$th ...
- 19.9k
9
votes
1
answer
404
views
Trinary Search Tree
I'm probably not the first to think this up, but here we go. An trinary search tree is a generalization of a binary search tree in the sense that instead of a comparison function returning true or ...
- 1,351
8
votes
3
answers
2k
views
Java TreeMap.floorKey() equivalent for std::map
I wanted something equivalent to this Java program:
...
- 181
8
votes
3
answers
834
views
Search string for a substring - indexOf
I am trying to write my own implementation of indexOf for learning purposes. I have an implementation of as follows. I'm sure a more efficient and shorter ...
- 91
8
votes
3
answers
6k
views
Scrabble algorithm review and performance suggestions
After finishing Project Euler 24, I decided to make a scrabble type of application using /usr/lib/dict as my dictionary what I cat that into a word file. It does take a few seconds, and the dictionary ...
- 317
8
votes
2
answers
192
views
8
votes
2
answers
12k
views
Implementation of Kosaraju's algorithm for strongly connected components
To learn and practice coding in C++, I wrote an implementation of Kosaraju's two-pass algorithm for computing the strongly connected components in a directed graph, using depth-first search.
This was ...
- 852