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
0
votes
0answers
14 views

optimising two parameter by binary search [closed]

I want to do 1076C problem of codeforces by binary search. But it is working of multiplication only and not optimising for addition. I have tried with the limits.link to the problem: https://...
4
votes
3answers
129 views

Binary Search Tree Using Templates in C++

I have made this BST using templates Node.h ...
5
votes
3answers
629 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
1k 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
69 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
71 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 ...
5
votes
0answers
126 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
76 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
35 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 ...
4
votes
2answers
135 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
91 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
278 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
119 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
62 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
62 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
101 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
39 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
166 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
137 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
58 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
318 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
81 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
174 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
59 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
61 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
44 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 ...
7
votes
3answers
596 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
246 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
2k 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
62 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
256 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
39 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 ...
2
votes
0answers
343 views

AVL Tree with delete method in Python 3

Just a general code review. I'm looking for my first developer job so anything constructive is awesome. Please, and thank you very much. I've written this implementation as an exercise and to add to ...
2
votes
1answer
80 views

Binary search tree with common operations

I trying to see if I implemented these operations correctly and if they could be optimized in any way. The implementations are just the typical implementations found online but I adjusted them to work ...
1
vote
1answer
207 views

Smallest number in BST which is greater than or equal to N

Given a Binary Search Tree and a number N, the task is to find the smallest number in the binary search tree that is greater than or equal to N. Print the value of the element if it exists ...
4
votes
1answer
217 views

Find largest smaller key in Binary Search Tree

Given a root of a Binary Search Tree (BST) and a number num, implement an efficient function findLargestSmallerKey that finds the largest key in the tree that is smaller than num. If such a number ...
0
votes
1answer
102 views

Binary Search Python

Tried to make a binary search algorithm, how did I do? ...
1
vote
1answer
196 views

Determining a salary for buying a house in 36 months

I did this programming challenge. Part C of the challenge, is to find the salary you have to save every month to be able to buy a house in 36 months. This is my first time using bisection search so I ...
1
vote
2answers
101 views

BST implementation for insert (put) and contain (search) in Python

I was asked about this question by my friend, so I decided to implement it recursively. I would like to get some code review. ...
3
votes
2answers
112 views

First Swing at an AVL Tree Implementation in C++

I've implemented a simple AVL binary search tree. For no real reason I decided to implement this without multiplicity, so if we try to insert(5) twice, it's only stored once in the tree. I've also ...
1
vote
2answers
70 views

Exercise 6.1 from ANSI C book - getword function

I have a following exercise from ANSI C book: Exercise 6.1. Our version of getword does not properly handle underscores, string constants, comments, or preprocessor control lines. Write a ...
1
vote
1answer
170 views

Binary search in Scala

Another exercise in Scala in which the goal is to find the target position as fast as possible. The initial input provides the grid size and the initial position. Each turn, this code provide a new ...
4
votes
1answer
300 views

Inefficient binary search? Hackerrank - Climbing the Leaderboard

I'm learning Golang and have been trying to get 100% on the following Hackerrank practice challenge: Climbing the Leaderboard The code passes ~8 of 11 tests. The Hackerrank tests are time-bound and ...
5
votes
1answer
79 views

Binary searching the turning point of a function

The problem You are given a list of \$ n \$ positive integers. Your task is to split the list into \$ k \$ subarrays so that the largest subarray sum is minimized. The input On the first line you ...
3
votes
1answer
265 views

Autocomplete implementation in Python

I have an autocomplete implementation in Python, and it passed all of the unit tests that I have included at the bottom. ...