Questions tagged [binary-search]

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

Filter by
Sorted by
Tagged with
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 ...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
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: ...
user avatar
  • 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 ...
user avatar
0 votes
0 answers
42 views

Python one-line binary search

...
user avatar
3 votes
3 answers
83 views

BinarySearchTree toString method

I have my ToString method right here for my BinarySearchTree class ...
user avatar
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. ...
user avatar
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 ...
user avatar
  • 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. <...
user avatar
  • 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? ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
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 ...
user avatar
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: <...
user avatar
  • 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 ...
user avatar
-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 ...
user avatar
  • 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. ...
user avatar
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: ...
user avatar
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-...
user avatar
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 (...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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: ...
user avatar
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 ...
user avatar
  • 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,...
user avatar
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 ...
user avatar
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, ...
user avatar
  • 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 ...
user avatar
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. ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
4 votes
3 answers
2k views

Binary Search Tree Using Templates in C++

I have made this BST using templates Node.h ...
user avatar
  • 345
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 ...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
-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 ...
user avatar
  • 9

1
2 3 4 5 6