Questions tagged [binary-search]
Binary search is an efficient algorithm for finding a key in sorted data. It runs in O(log n) time.
289
questions
6
votes
1
answer
100
views
Implementation and Testing of Exponential Search for scenario where we search the same array/list many times
Exponential Search is an optimization over binary search.
Conceptually, when searching for a number target in a list of numbers ...
- 328
1
vote
3
answers
94
views
Calculating square roots using binary search
I'm trying to find the square root of a number (num) using binary search in Rust. I'm new to Rust, but I've done quite a bit of programming in other languages, ...
- 111
1
vote
2
answers
107
views
Duplicate Binary Search Improvements
I'm working on an implementation of binary search (in Python) that can operate on a sorted array that may have duplicate elements.
I've written a submission that has managed to hold up against my test ...
- 11
1
vote
1
answer
47
views
Counting the array spots visited by binary searches (Java)
So the idea was to find out how many times each array component is considered by binary search when we search all possible needles for the haystack:
...
- 25.7k
6
votes
1
answer
129
views
Binary search algorithm (Python 3.9)
New to using this platform and would like to familiarise myself with it so would just like to ask if I am exhibiting good practice with my programming.
Started the online CS50 course today and thought ...
- 63
0
votes
0
answers
42
views
3
votes
3
answers
83
views
BinarySearchTree toString method
I have my ToString method right here for my BinarySearchTree class
...
- 51
1
vote
2
answers
125
views
size() method for a binary search tree
This is my size method for my binary search tree, that is meant to implement recursion to calculate the tree's size.
...
- 51
0
votes
0
answers
61
views
Stamp Combination Kattis
I tried to solve Stamp Combination problem on Kattis, which basically gives an integer array and a target number. The problem asks whether we can find a contiguous subarray which starts at either end ...
- 21
3
votes
2
answers
156
views
Binary Search of Array in C#
I am an algo-newbie and this is my first attempt at writing binary search and it worked on the first try. But something about it tells me that its far from perfect. Please tell me how I can improve.
<...
- 133
1
vote
2
answers
64
views
Binary Search using recursive approach
Is the following implementation of recursive function correct? How about the time complexity of the code; is it good in terms of performance?
...
1
vote
1
answer
125
views
HackerRank - Climbing the Leaderboard: I don't understand why my code is exceeding the time limit
Climbing the Leaderboard
An arcade game player wants to climb to the top of the leaderboard and
track their ranking. The game uses Dense Ranking, so its leaderboard
works like this:
The player with ...
1
vote
1
answer
46
views
Finding the closest values in a sorted list that don't go under/over
For my project I have a sorted array of objects of timestamps (in milliseconds) and I need two functions. One function should find the closest time that doesn't go over a specific amount, and the ...
- 193
2
votes
1
answer
36
views
Recursive Binary Search in Typescript
I've ran a few tests, not extensive though, and it apparently works. Like many standard binary search algorithms, if the number returned is < 0, you can take the complement (~) of the returned ...
- 219
0
votes
2
answers
87
views
Python list subclass with O(1) prepend / How to get bisect to work with reverse sorted list
For a particular problem, I need to have a list that:
supports O(1) prepend, and
that I can call bisect.bisect_left on, which ...
- 328
0
votes
1
answer
67
views
Climbing the leaderboard (Hacker Rank) via binary search
I am trying to solve the Climbing the leaderboard problem on Hacker Rank. My code passes all the test cases except Test Cases 6 to 9, which I assume are using large data sets.
I'm using binary search ...
- 43
0
votes
1
answer
93
views
Binary search to find the closest element
I wrote a binary search to find the closest element to x in an array. How can show the correctness of the algorithm for any cases? Because it handles with floating points and variable length arrays, ...
- 77
4
votes
1
answer
75
views
JavaScript Binary Search -- first try
EDIT: code snippet added, check the output in JS console
I wrote the following binary search algorithm in JS, for the first time in my experience. The variable ...
- 143
1
vote
2
answers
453
views
Search Method In Python / Python 3.9
I have implemented Binary_Search in python (I think), and my own method for range objects. I want to know if there is any way to improve this code, here it is:
<...
- 83
0
votes
1
answer
51
views
Finding inorder successor of a BST in C [closed]
Please review this code
I have written a function to find the successor of BST in c. It takes three arguments, i.e root pointer to the binary search tree, node value of which we have to find a ...
-2
votes
2
answers
65
views
Binary Search Algorithm Difference
As far as I test, there is no any bug point tested. However, I wonder that if there is a problem with the usage of arr.Length or ...
- 393
1
vote
2
answers
76
views
How can I optimize this Binary Search Tree?
I've added some methods to a basic BST implementation for integers - if anyone can point out some ways that this could be written in a more efficient or clean manner, please let me know.
...
1
vote
1
answer
92
views
How to make this special binary-search algorithm more rusty?
I am solving one binary search problem in LeetCode.
I have accomplished such code:
...
1
vote
2
answers
236
views
Sorting and Searching Algorithm
The searching algorithm that I created is dependent upon the sorting algorithm (which many of you have seen in my previous question). I believe that the sorting algorithm can't be better (for beginner-...
- 442
6
votes
0
answers
68
views
Subtracting elements of datasets of an HDF5 file
I am trying to solve the following problem:
Input: Input is two arrays (Nx4, sorted in column-2) stored in datasets-1 and 2 in HDF5 file (input.h5). N is huge (...
- 61
1
vote
1
answer
92
views
Binary Search recursive & iterative solution
I have implemented binary search solution by using recursion and iterative approach.
I there any way to improve it?
Tests
...
- 880
7
votes
1
answer
728
views
x64 NASM Assembler: Binary Search
While quarantine I decided to look into the assembly language, as it's quite interesting to see how code works on the lower levels. To challenge myself I made a binary search algorithm. The OS is ...
1
vote
1
answer
161
views
Faster binary search to find the index in Python?
I am implementing a binary search algorithm and my code is as shown bellow:
...
- 325
2
votes
1
answer
572
views
Count number of previous elements greater than its element at present index
Suppose I have a vector containing n elements. I want to find out the number of previous elements greater than its element at present index i. I want to find ...
- 21
2
votes
1
answer
111
views
Leetcode Search in Rotated Sorted Array
I was doing Search in sorted array question from leetcode
Question
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,...
- 465
2
votes
2
answers
85
views
Basic binary search in python
I just started learning to code during quarantine and whilst learning python, I created this program for a binary search. This is really basic so I assume that there is a way easier method. If anyone ...
- 23
2
votes
3
answers
247
views
Comparing binary insertion sort with straight insertion sort in Java
Straight insertion sort
When inserting an element into its proper location to the left, one can achieve that by \$n\$ adjacent swaps which totals to \$3n\$ assignments. Straight insertion sort, ...
- 25.7k
2
votes
1
answer
202
views
Binary Search implementation: HackerRank - Climbing the Leaderboard
My code passes 11 out of 12 test cases. I was wondering where I can improve my code. NOTE: This code needs performance improvement, as it is working for most of the cases. To mu knowledge it would ...
- 37
3
votes
2
answers
262
views
Sorting an array using a Binary Search Tree with C++
Given an array of integer (all different from each other), this program creates a BST with the array elements in order to sort them and put them back into the array, using the BST properties.
...
- 43
3
votes
1
answer
36
views
I need to know that if everything okay in my BTS put and get method
I implement BinaryTree (K extends Comparable, V) concept to binarySearchTree and I have written get and put method. As far as I check, there is no problem in my code. So now I wonder that are there ...
2
votes
1
answer
1k
views
Simple BST implementation using C++ Struct
I am trying to implement DSs in C++ and this is BST insert and search functions. I tried in two different ways, please review and see if one is advantageous over other.
With pointer to pointer
...
- 145
3
votes
2
answers
581
views
Simple Binary Search Tree Class with Insert and Search Functions
I am trying to learn to implement DSs in C++ and here is a simple implementation. Please review in terms of optimization, memory management, coding standards, etc
...
- 145
4
votes
3
answers
2k
views
5
votes
3
answers
688
views
Searching an element in an alternately sorted array
I had to write some code that receives a number 'x' and an alternately sorted array (an array with all even indexes sorted upwards and all odd indexes sorted downwards) and checks if 'x' exists in the ...
- 181
11
votes
4
answers
3k
views
Binary Search given sorted array Unit test
I have implemented Binary search code for a given sorted array, written unit test too, Please review my BST unit test code and let me know your comments for improvements.
...
- 175
1
vote
2
answers
139
views
Semi sorted binary search
Say you have an array that is "semi-sorted", e.g. something like this:
[7,8,9,10,1,2,3,4,5,6]
Where a part of the end of the sorted array was transferred to the beginning.
Is there a way to still ...
- 607
5
votes
1
answer
2k
views
Calculating the average of all nodes in a Binary Search Tree using visitors
I'm required to calculate the average value of all nodes in a BST using a Visitor, I'm not sure if I did this correctly or if i could just calculate the average ...
- 51
6
votes
1
answer
166
views
Implementation of container searchable by any element
Writing game engine as a hobby, I've come across many situations where I need a container like a map, but searchable by different keys: a block allocator where a block needs to be searched by either ...
- 61
5
votes
2
answers
779
views
Binary search guess game in C++
I'm trying to write a program where computer attempts to guess a number entered by user. Computer should keep asking until guessed number will be equal to user number.
If you know what can be ...
- 51
1
vote
0
answers
47
views
BST range search
I'd like some input on my implementation of bst-range, which follows below.
Before we can get to bst-range, we first need some setup code to build the BST.
(You ...
- 483
3
votes
2
answers
340
views
Binary Search Tree implementation in Python 3
Please review my BST Code
1. Class node
class Node:
2. Constructor
...
- 456
4
votes
1
answer
92
views
Flexible Binary Search
This search consists of two functions QuickMatch() which searches for the value and getQuickRowValue() which returns the value ...
- 4,028
3
votes
1
answer
251
views
LeetCode: Time Based Key-Value Store C#
https://leetcode.com/problems/time-based-key-value-store/
Create a timebased key-value store class TimeMap, that supports two
operations.
...
- 5,329
4
votes
1
answer
578
views
Compute the square root of a positive integer using binary search
The requirement is to find the square root of a positive integer using binary search and the math property that square root of a number n is between ...
- 391
-1
votes
1
answer
978
views
Python 3 code for a binary search tree [closed]
I am working on a python3.6.5 question about BST:
Binary search tree (BST) is a binary tree where the value of each node is larger or equal to the values in all the nodes in that node's left ...
- 9