Binary search is an efficient algorithm for finding a key in sorted data. It runs in O(log n) time.
3
votes
1answer
22 views
Shell binary search with sorted input
I have coded binary search in shell, just for practice.
Input
Input data is already sorted set of numbers streamed to the script. $1 is the sought number.
...
2
votes
1answer
50 views
Efficiency of binary search and improvements
Below you can see my binary search method, and as a relatively new programmer I am looking for any suggestions on how it could be improved.
...
1
vote
2answers
154 views
Sorting an Integer array
The program sorts the array from lowest to highest and outputs the index of the searched value:
...
3
votes
1answer
49 views
Substring searching with Knuth–Morris–Pratt
My program uses the Knuth–Morris–Pratt algorithm to search for a particular substring in a .txt file and then store it in a binary search tree.
Note that ...
4
votes
3answers
110 views
Binary search tree implementation (with Node class)
I have implemented the Binary Search Tree in Java and would love to get reviews. I would like to have some comments on multi thread implantation.
Note: Corrected Code is in the Answers
...
3
votes
2answers
43 views
Binary search feedback and improvements
I implemented the binary search algorithm. Input vector is sorted by < than operator implemented by type T. The less than ...
4
votes
3answers
153 views
Recursive Level Order traversal
I have come up with this code to do level order traversal recursively for a binary search tree.
...
5
votes
4answers
572 views
Simple Binary Search Tree
At the moment I am learning algorithms and here I am trying to implement a simple binary search tree. I would like to know your suggestions on whether I am on the right track or not, and how this can ...
3
votes
2answers
93 views
Epilogue to a binary search to find the range of matching indexes
I am trying to find out the best practice for writing a loop which does one check and at the same time has to increment a value so that the while loop will ...
5
votes
1answer
91 views
Enter values, generate a list, and search
My assignment in school:
Read in names to sort until the user types the “enter” key
After sorting and displaying the array of strings
Do a binary search to find if the string is in the array
If the ...
4
votes
0answers
80 views
Persistent segment tree
I'm trying to solve this problem.
Given a sequence \$B=B_0,B_1,\ldots,B_{N−1}\$
for each query \$(P,K)\$, find the minimum \$S\$
s.t. there are at least \$K\$ entries in \$B\$ that satisfies
...
2
votes
1answer
102 views
Binary Search Tree in C
I have implemented a BST from scratch. My aim is to draft better code and understand some pitfalls which I may have overlooked.
It includes the following functionalities:
Insert a new item.
Find ...
4
votes
2answers
140 views
Binary search that returns bitwise complement of missing index
While re-writing some old JavaScript code to better handle large arrays, I ended up writing my own binary search method.
I found many examples of binary search methods written in JavaScript, but all ...
4
votes
1answer
94 views
Find string in sorted array with interspersed empty strings
(from McDowell) Given a sorted array of strings which is interspersed with empty strings, find the location of a given string.
eg. "ball" in
...
1
vote
1answer
71 views
Find the peak element using BS
A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that ...
2
votes
0answers
36 views
Basic Binary Tree in Go
As an exercise I have written a basic binary tree implementation in Go.
Tree struct:
...
1
vote
2answers
199 views
Simple peak finder solution - O(log n)
I attempted a solution to a seemingly simple problem:
Peak Finder
Let input be a list. input[i] is a peak if ...
11
votes
3answers
151 views
Karate Chop Kata
I had some time to kill today, and I found the Karate Chop Kata.
Specification:
Write a binary chop method that takes an integer search target and a sorted array of integers. It should ...
1
vote
1answer
161 views
Binary search using recursion, iteration, shifted array
Interview question some engineer, asked me to write binary search in 2 ways,
Also asked me to write binary search on a shifted array (10 20 1 2 3 4).
Wrote that and then asked me to find the offset ...
1
vote
1answer
38 views
insertBST exercise
I'm just learning Haskell on my own, and did an exercise to implement insertBST.
Is this idiomatic Haskell?
...
6
votes
1answer
725 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 ...
2
votes
1answer
78 views
Binary Search in C
The standard C library function bsearch wasn't giving me correct results, apparently. So I decided to implement a binary searching function in place of it. It ...
5
votes
2answers
470 views
Binary Search Tree in Ruby
Binary Search Tree, with preorder traverse. What other methods should I add? How can I improve it?
...
2
votes
0answers
52 views
Mini Binary Tree “library”
This is my first attempt at learning binary trees. I'm looking for general feedback on how it could be made cleaner, more idiomatic, or more efficient.
...
3
votes
2answers
1k views
Read binary file by blocks
I wrote a function that allow me to read a binary file using 3 blocks what ever the length of file.
I've decided to divide the length of my file into 3:
block 1: ______________
block 2: ...
3
votes
0answers
39 views
BST remove implementation
As practise, I implemented a BST and also the remove() method, but I figured I always have to check if the node being deleted is coming from the left child or the ...
3
votes
3answers
3k views
Binary search tree with tree traversal
Although there are several implementations of binary search tree, I have made my own implementation for practice. The following code does the followoing operation
- Create a binary tree
- search ...
5
votes
2answers
157 views
UniqueList Class in VBA
I often find myself abusing dictionary objects just for the exist method like this,
...
1
vote
2answers
227 views
Binary search as a generic algorithm
I am upgrading my C++11 knowledge and repeating some essential algorithm. Here is binary search only in terms of iterators.
...
5
votes
2answers
437 views
Binary search: first/last/random occurrence
I've written some code to "binary search" a list, and return the first occurrence of the target:
...
7
votes
1answer
434 views
1
vote
2answers
69 views
Binary Insert Method - handling edge cases
I've created a function that uses binary search to insert an element into an array (similar to this question). I haven't benchmarked it, but based on my knowledge it should get \$O(1)\$ in the best ...
1
vote
1answer
100 views
1
vote
2answers
952 views
How to search for a word in a sorted text file efficiently?
I want to write my own program to search for a word in a sorted text file. In the text file each word is in one line. I want to write this myself because I did not find any simple program (without ...
10
votes
7answers
4k views
Find the duplicate in a sorted array In less-than O(n)
Assumptions:
The array is sorted.
There is only one duplicate.
The array is only populated with numbers [0, n], where n is the length of the array.
Example array: [0,1,2,3,4,5,6,7,8,8,9]
...
3
votes
2answers
310 views
BinarySearch Tree implementation & traversals
I am practicing various tree algorithms and that require code review for it's efficiency, clarity and also if it can be made better etc.
Is there a better way to call ...
12
votes
6answers
2k views
Binary search use in simple guessing game
I'm making a simple guessing game in C. Basically what I need is some help double-checking my work, more specifically a verification that the my binary search in my case statements look okay. The goal ...
1
vote
0answers
34 views
Binary search with heurisitcs or something else
Currently I'm using a binary search algorithm to search an index of a tree that represents an XML file.
Can I use heuristics to improve the search? What can I do to improve this search function?
...
5
votes
1answer
913 views
Searching in a sorted 2D matrix
If I was at an interview, and wrote this code, what would you think? Please be brutal.
Time it took to wrote it: 13 minutes
Problem:
Write an efficient algorithm that searches for a value in an ...
5
votes
1answer
272 views
BinarySearch Kata in Ruby
I've just completed this binary search kata - which has some weird requirements - and I spent a little while "cleaning" up my code and making it more compact. I would appreciate some feedback on the ...
7
votes
2answers
459 views
Can this recursive binary search in C be made more concise?
Can someone please let me know if they see glaring issues with this code? I tested a handful of cases and it seems to work but in other threads. I often see much more concisely written versions of ...
5
votes
3answers
7k views
1
vote
1answer
196 views
Find last zero in infinite stream of 0's followed by 1's
Given an infinite stream with the property, such that after all 0's there are only all 1's, find the index of the last 0.
I'm looking for code review, best practices, optimizations etc. Verifying ...
1
vote
1answer
2k views
Search an element/item in an n-ary tree
Search an element in a n-ary tree. Looking for good code practices, optimizations etc.
If question is ambiguous, let me know and I will reply ASAP.
Note - ...
3
votes
4answers
1k views
Median of two sorted equal sized arrays on combination
The comprehensive description of the problem can be found here. I'm looking for code review, clever optimizations, adherence to best practices. etc.
This code is also a correction of code previously ...
2
votes
1answer
113 views
Is this binary search in TypeScript correct?
I need your help to see if the following binary search code is correct. I did my best to cover the corner cases. I wonder if I missed anything.
The code as it is with tests (you can play with it ...
4
votes
2answers
347 views
Testing to see if tree is BST
I found a function online that tests if a tree is a binary search tree:
...
7
votes
3answers
251 views
Finding an element in a list
I'm kind of new to Python. So, I wonder which method is better to use in a function to find an element in a list.
First:
...
2
votes
2answers
521 views
Binary search in rotated sorted array
Looking for code review, optimizations, good practice recommendations etc.
...
5
votes
2answers
5k views
Binary search for inserting in array
I have written a method that uses binary search to insert a value into an array.
It is working, but i would like to get a second opinion to see if i didn't write too much code for it. aka doing same ...
