Binary search is an efficient algorithm for finding a key in sorted data. It runs in O(log n) time.

learn more… | top users | synonyms

1
vote
2answers
46 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 ...
0
votes
2answers
83 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
2k 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
145 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 ...
11
votes
6answers
1k 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
30 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
110 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
84 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
422 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
2k views
1
vote
1answer
76 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
348 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
607 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 ...
3
votes
1answer
62 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
98 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
120 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
138 views

Binary search in rotated sorted array

Looking for code review, optimizations, good practice recommendations etc. ...
5
votes
2answers
1k 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 ...
3
votes
5answers
387 views

count all array[index] == index occurrences

The method foo gets a sorted list with different numbers as a parameter and returns the count of all the occurrences such that: ...
5
votes
2answers
489 views

Finding greatest value in array smaller than x

Code review requested to make this code simpler, cleaner, and better. Input array is sorted. This program finds the greatest number smaller than x. So, in an ...
6
votes
1answer
187 views

Is this implementation of binary search correct?

Is this implementation of binary search correct? Any special or edge cases that I missed out? Maybe it should be optimized for elements that are less than the first element of the array or greater ...
1
vote
2answers
123 views

Binary search on cstrings

This implements binary search on an array of cstrings. One thing I'm wondering about is it faster or slower to pass a variable as const i.e. len. Also ...
2
votes
2answers
297 views

Generic binary search tree implementation

I use this interface for my BST node class: ...
5
votes
1answer
122 views

Duplicate detection and reporting in a BST

For the purpose of this problem, the BST is defined to allow duplicates, and the duplicate values will always follow to the right-side of the parent nodes with the same value. For example, with the ...
3
votes
1answer
273 views

Binary Search Tree insert method (map interface)

This is my implementation based on Map<K,V> interface. The BST is a linked binary tree with root reference, both internal and external nodes (...
2
votes
1answer
296 views

Custom linked list class

I put together a Custom Linked List class in hopes of using it for a Talent/Skill Tree for a game. It allows for inserting nodes with NSMutableDictionary for ...
2
votes
1answer
169 views

First Occurrence of Number in Binary Search?

I am trying to write a function, where given a sorted array, and a number, it returns the FIRST index of that number. Is this correct? Code is in Ruby, but even if you don't know Ruby, you can pretty ...
1
vote
2answers
135 views

Fast integer handling

Each data structure has it's own time complexities. The biggest one that jumps out at you is the hash table. The average times for Insertion, Deletion and Searching are all O(1). But it's really ...
1
vote
1answer
75 views

Binary Search Feedback

I have written a binary search algorithm, but it seems to be a bit different than other peoples that I've seen. I was hoping that the community could give me some feedback as to whether or not I'm ...
4
votes
4answers
1k views

Check if a Binary Tree <String> is aBinary Search Tree

I'm understanding the question, but I want to know whether or not my implementation is correct. The question is: Write a method that accepts as its argument a BinaryTree object and returns true ...
2
votes
1answer
234 views

Finding the max subset of non-overlapping intervals

How could this code become cleaner? I think that the way I handle the interfaces and binary search could be improved. I am trying to understand how to structure such a code (and usage of APIs) in a ...
3
votes
1answer
486 views

Returning Binary Search Tree Nodes in Zig Zag manner

I tried to implement an answer for the algorithm question given below. I implemented two different solutions. I couldn't decide which one is better. ( Maybe none ) Note: Node class and ZigZag ...
2
votes
0answers
195 views

Binary search algorithm for non-overlapping time spans and possible gaps

I have a data structure, containing time span nodes, with the following properties: Nodes are sorted ascending Time spans will not overlap, but may have gaps between them Each node will have a start ...
1
vote
1answer
155 views

Errors with binary search in Haskell

I just learned about Maybe in Haskell, so I decided to try to use it with a binary search. Here's the function: ...
0
votes
3answers
911 views

Searching for an element in a 2D array

For example, given a 2D array (a matrix): {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}} What are the solutions to find a number, such as 6? Here's the code I ...
5
votes
1answer
9k views

Binary search tree implementation in C++

I've written a BST implementation and would like a code review and any suggestions on how to make it better. ...
3
votes
2answers
296 views

UVA 10474 - “Where is the marble?” time limit

I have a problem from UVA online judge here. I have read it tons of times, and as they said, I have to get the answer really fast. I have used a binary search and ...
0
votes
3answers
385 views

Optimizing function that searches for binary patterns [duplicate]

Possible Duplicate: Optimizing function that searches for binary patterns I have two functions that calculate whether or not a given coordinate (x, y) is a diagonal or anti-diagonal of ...
4
votes
2answers
639 views

Number-guessing game in C#

I have just written a solution to the following problem: We all know the classic "guessing game" with higher or lower prompts. lets do a role reversal; you create a program that will guess ...
1
vote
2answers
19k views

Deleting a node from a binary search tree

I have read about it at a few places and tried to write my own version. I would like to get it reviewed. ...
7
votes
1answer
1k views

Implementations of prefix lookup tables in Python

I've got a fairly performance sensitive need for fast prefix lookup, and I've built two different implementations trying to optimize for my use case. The first is built off a Trie implementation, and ...
2
votes
2answers
3k views

Splay tree implementation

I am looking into splay trees and I implemented a version. It seems correct. Could someone please let me know if this indeed correct and how to improve it? I will just show the ...
3
votes
1answer
305 views
7
votes
5answers
965 views

Java binary search (and get index if not there) review

I want to do binary search and if the target is not there get the index of where it should have been. This is the code I came up with. It seems correct. Is there any problem? Can it be improved? ...
3
votes
1answer
2k views

Binary tree traversal algorithms

I recently started learning binary tree. Following is the code for a typical node for a tree (no code review required for that): ...
2
votes
2answers
3k views

Generic binary search

I have the following code for binary search ...
1
vote
3answers
768 views

Binary search optimization: Kernighan & Ritchie 3-1

The problem I am trying to solve can be described as take binarysearch0 and rewrite it as binarysearch1 such that ...
3
votes
1answer
414 views

Binary search with strings

I wrote a quick and dirty program to perform binary search with an ordered array (list) of C style strings. For example: {"1", "12", "23", "124"} etc (though my ...
5
votes
7answers
7k views

Efficient Binary Search

My implementation: ...