Questions tagged [binary-search]
Binary search is an efficient algorithm for finding a key in sorted data. It runs in O(log n) time.
266
questions
6
votes
0answers
36 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 (...
1
vote
1answer
72 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
...
7
votes
1answer
48 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
1answer
45 views
Faster binary search to find the index in Python?
I am implementing a binary search algorithm and my code is as shown bellow:
...
2
votes
1answer
132 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 ...
0
votes
0answers
36 views
Implement sorted list and BST as sorted maps in Python
I have implemented both sorted list and binary search tree as sorted maps in Python. Both are subclasses of MutableMapping. Apart from the usual methods of ...
2
votes
1answer
61 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,...
2
votes
2answers
74 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 ...
2
votes
2answers
58 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, ...
2
votes
1answer
75 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 ...
3
votes
2answers
114 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.
...
3
votes
1answer
31 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
1answer
79 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
...
3
votes
2answers
110 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
...
4
votes
3answers
231 views
5
votes
3answers
644 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 ...
11
votes
4answers
2k 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.
...
1
vote
2answers
75 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 ...
5
votes
1answer
365 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 ...
6
votes
0answers
136 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 ...
5
votes
2answers
187 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 ...
1
vote
0answers
38 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 ...
3
votes
2answers
228 views
Binary Search Tree implementation in Python 3
Please review my BST Code
1. Class node
class Node:
2. Constructor
...
4
votes
1answer
81 views
Flexible Binary Search
This search consists of two functions QuickMatch() which searches for the value and getQuickRowValue() which returns the value ...
3
votes
1answer
135 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.
...
4
votes
1answer
367 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 ...
-1
votes
1answer
353 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 ...
2
votes
0answers
168 views
Find Single Element in a Sorted Array, from LeetCode
The problem quoted:
https://leetcode.com/problems/single-element-in-a-sorted-array/
Given a sorted array consisting of only integers where every element appears exactly twice except for one element ...
-2
votes
1answer
60 views
Challenge - Construct binary tree from array [closed]
A coding challenge to construct a binary tree from an array.
...
1
vote
1answer
68 views
Inventory system codebase
I'm here looking for a review over my current code-base.
Please:
Ignore using namespace std; this is for educational purposes mostly so the usage of using namespace std; does not matter for this ...
3
votes
2answers
107 views
codekata: Binary search on an int array
I'm following Karate Chop kata for a binary search. I really wanted to avoid built in functionality within the language. I'm pretty new to C# so any recommendations is greatly appreciated.
Spec: ...
1
vote
0answers
42 views
Binary Search Tree to store objects now with improvements
Objective:
I'm trying to create a BST in order to insert Packet objects for search purposes. Packet holds information like partId, ...
9
votes
3answers
1k views
Binary Search in C++17
Question
Any way I can optimize this further with C++11 or C++17 features?
Would also like feedback on my variable naming, memory management, edge case handling (in this someone calling my function ...
4
votes
2answers
184 views
Project Euler Task 42 Solution
I am relatively new to programming and have been recommended to work through the many tasks in order, in order to better my skills. For some reason, problem 42 had me stumped for a while:
The nth ...
4
votes
5answers
168 views
Find the smallest element in a sorted and rotated array [closed]
I was solving a question asked in interview by Uber. It says:
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum element in \$O(\log n)\$...
4
votes
0answers
60 views
Array Search Algorithm
Recently, I've been experimenting with an array searching algorithm that I'm not sure I've seen anywhere (minor references here).
I'm still not fully-learned on how to state the efficiency of what I'...
4
votes
1answer
471 views
Building balanced BST from sorted array: recursive and iterative approaches
I am implementing an algorithm to solve the following problem:
Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal ...
4
votes
1answer
89 views
Generalisation of Binary Search
I wrote a function to implement a generalised version of binary search that can find the minimum or maximum index in a given sorted list that satisfies a provided predicate.
My Code
...
3
votes
1answer
226 views
AVL height-balanced binary search Tree and Dictionary in C# v2
Mostly as a learning exercise, and partly as I thought it might be useful, I have written an implementation of AVL trees ( https://en.wikipedia.org/wiki/AVL_tree ).
An AVL tree is a height-...
0
votes
1answer
81 views
Find array index with element equality in Python
I was given this question during an interview. It is similar to binary search and I would like to ask for feedback for my solution.
Array Index & Element Equality
Given a sorted array arr ...
0
votes
1answer
86 views
Binary search a sorted list of integers in Python 3
y is the value I am searching for. Is this the correct implementation for binary search?
...
3
votes
1answer
48 views
Extended Binary Search Function (python)
I wrote a function to find the closest value in a list to a given search value. What prompted me to write it was as boilerplate for a prime number problem so I could find the closest prime to a given ...
6
votes
3answers
612 views
Binary search for students
I'm putting together an example for students where I would like to show how we can optimize even such basic algorithm like a binary search with respect to hardware. I do not consider threads. I wrote ...
7
votes
2answers
1k views
Cleaner way to handle double pointer in C++ BST?
I have an implementation for my first binary search tree in C++. I was wondering if there was some cleaner way to avoid using the double pointer in the way I have my code setup? Such as on one line I ...
0
votes
1answer
501 views
Search insert position
I am trying to solve this problem:
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
and ...
3
votes
1answer
3k views
Binary search tree in C++, and display, search and delete functions
I feel ready to show you my work on creating BST in C++ using double linked list and 3 more functions for manipulating the tree. There is also one more function checking if the tree is real or not.
...
0
votes
1answer
53 views
Find the square root of the number without using any built-in function?
I am working on below problem:
Given an integer, how do you find the square root of the number
without using any built-in function?
...
2
votes
1answer
90 views
Leetcode #826. Most Profit Assigning Work solution in Java (Sort + Binary Search)
Problem Statement:
We have jobs: difficulty[i] is the difficulty of the ith job, and profit[i] is the profit of the ith job....
1
vote
1answer
324 views
Find maximum in sorted and rotated array
This is an interview question.
A sorted rotated array is a sorted array which was rotated 0 or more times.
For example: [1,2,3] -> [2,3,1]
...
2
votes
0answers
41 views
Find target in sorted array pivoted at some unknown point in O(log n)
You are given an array sorted in ascending order which is rotated at
some pivot unknown to you beforehand. Find your target in \$O(log n)\$
which means it should be a binary search. If the value ...
