We changed our privacy policy. Read more.

Questions tagged [search]

This tag is for questions about search algorithms, tools, and technologies.

Filter by
Sorted by
Tagged with
149
votes
18answers
30k 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 ...
50
votes
12answers
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 ...
38
votes
5answers
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 ...
31
votes
4answers
78k views

A* search algorithm

NodeData stores all information of the node needed by the AStar algorithm. This information includes the value of ...
30
votes
8answers
49k 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 ...
29
votes
5answers
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 ...
26
votes
6answers
205k 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? ...
20
votes
2answers
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 ...
19
votes
4answers
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 ...
17
votes
7answers
140k 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 ...
15
votes
2answers
361 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 ...
14
votes
4answers
442 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 ...
14
votes
2answers
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 ...
12
votes
5answers
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 ...
12
votes
5answers
8k 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 ...
12
votes
3answers
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 ...
12
votes
2answers
598 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,...
12
votes
1answer
155 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 ...
11
votes
4answers
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 ...
11
votes
2answers
16k 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? ...
11
votes
2answers
853 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 ...
11
votes
2answers
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, ...
11
votes
1answer
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, ...
11
votes
2answers
157 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 ...
11
votes
1answer
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 ...
10
votes
3answers
574 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 ...
10
votes
1answer
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. ...
10
votes
4answers
289 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 ...
10
votes
2answers
572 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 ...
10
votes
1answer
468 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....
10
votes
1answer
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 ...
10
votes
2answers
435 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 ...
10
votes
1answer
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 (...
10
votes
1answer
403 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 ...
10
votes
1answer
341 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-...
10
votes
1answer
173 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 ...
9
votes
5answers
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 ...
9
votes
3answers
21k views

Get values between two dates

I have a search form where users can enter ValidFrom and ValidTo dates, There are three conditions: ...
9
votes
4answers
241 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, ...
9
votes
2answers
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 ...
9
votes
3answers
3k 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 \$...
9
votes
2answers
966 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 ...
9
votes
1answer
322 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 ...
8
votes
3answers
1k views

Java TreeMap.floorKey() equivalent for std::map

I wanted something equivalent to this Java program: ...
8
votes
3answers
792 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 ...
8
votes
3answers
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 ...
8
votes
2answers
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 ...
8
votes
1answer
6k views

Excel VBA binary search class module [closed]

I have a long list of sorted strings in a Workbook, and I have to find a lot of values in it. I was hoping to build a binary search Class Module that will find them for me faster than Excel's built-in ...
8
votes
1answer
10k views

A* Search on 'Map of Romania' (Russel and Norvig ch3) in Python 3

I've implemented A* search using Python 3 in order to find the shortest path from 'Arad' to 'Bucharest'. The graph is the map of Romania as found in chapter 3 of the book: "Artificial Intelligence: A ...
8
votes
1answer
2k views

Fuzzy / approximate text matching program in Python

I'm trying to build a program that will find approximate text matches between two texts. Basically, I'd like to find a way of identifying quotations, so that when an author quotes, say, the King James ...

1
2 3 4 5
8