Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [binary-search]

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

7
votes
2answers
848 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
33 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
162 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
46 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
38 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
59 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] ...
0
votes
0answers
28 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 does not ...
2
votes
0answers
96 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
70 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
75 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
117 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
79 views

Binary Search Python

Tried to make a binary search algorithm, how did I do? ...
1
vote
1answer
97 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
52 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
86 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
46 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
91 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
132 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
62 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
170 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. ...
4
votes
2answers
66 views

Binary search on a uniformly distributed vector

I am trying to write a binary search using recursion in C on a sorted vector that we can assume comes from a uniform distribution between the start and end values. What I am trying to write is an ...
0
votes
2answers
145 views

Binary search for integers

I've written binary search with only my own efforts 💪💪 without glancing at anywhere. I stuck on finding base case. At final, I think that if last checking is less than first index or first checking ...
0
votes
1answer
825 views

Perform BFS on a Binary Tree

Task: Perform Breadth first traversal on a Binary Search Tree and print the elements traversed. ...
6
votes
1answer
135 views

Searching the Array Index & Element Equality

I was asked this question from online coding interview and I have provided my solution that passes all of the test cases. I wanted to see if someone can review my code. Array Index & Element ...
0
votes
0answers
42 views

findInOrderSuccessor in a Binary Search Tree python

I would like to ask code review for the following problem that I solved. https://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/ ...
3
votes
1answer
107 views

Python Binary Search Performance

This is my version of the binary search method. What more can I do to optimize this? I have written comments throughout to guide anyone who might find this code helpful through how it operates. But I ...
4
votes
1answer
163 views

Binary search on a Bitonic array

So, I have been preparing for an interview and I thought of coding up a Binary search on a Bitonic array for practice. A bitonic array has a bunch of numbers in increasing order at the beginning of ...
2
votes
0answers
300 views

Three sum using binary search

Given an array and a value, find all the triplets in the array whose sum is equal to the given value. For example, if the given array is {12, 3, 4, 1, 6, 9} and the ...
5
votes
1answer
133 views

Binary Search Tree C++

Appreciate your thoughts and feedback... BST.h ...
0
votes
2answers
94 views

Simple binary search

Here the task (in Indonesian). I think my binary search algorithm is correct. Ideone ...
10
votes
1answer
152 views

Using bisect to flip coins

I am trying to solve this problem on Codechef, which has a list of \$N\$ coins, all initially tails-up, and a list of \$Q\$ commands. There are two possible commands, ...
3
votes
3answers
663 views

Counting the number of 1 bits in a sorted bit array

I wrote a function in python to count the number of 1-bits in a sorted bit array. I'm basically using binary search but the code seems unnecessarily long and awkward. I did test it for several ...
3
votes
1answer
102 views

Binary search for IOI problem: Cave

Question http://www.ioinformatics.org/locations/ioi13/contest/day2/cave/cave.pdf Code ...
5
votes
1answer
100 views

iterative binary_search Python implementation

I did a Python implementation of binary search implementation iteratively. It passes all of the test and I was wondering if I can get any feedback. ...
1
vote
2answers
206 views

binary search using recursion [closed]

I implemented a binary search algorithm using recursion in Java package com.soloworld.binarysearch; ...
1
vote
1answer
48 views

Getting partition boundaries in sorted integer array using only equalTo operator

For my task, I need to find partition boundaries in sorted input. Values are expected to be repeated, I just need to find range for each value. Please check comment in following output for example. ...
1
vote
1answer
78 views

Binary search large tree in C

I tested creating 1 billion (1,000,000,000) nodes and lookups are fast. You can ask for a node by node_id. ...
4
votes
1answer
122 views

Rare binary numbers

Rare numbers are the natural numbers in their binary forms in which there aren't two (or more) ones next to each other. Make a program that will give the N. rare number! For example: In case of N =...
2
votes
1answer
1k views

Loop for inserting a node into a binary search tree

I am trying to implement binary search tree. One method which I am trying to implement in the most efficient and stylish way is node insertion. I am under the impression that while (true) is a bad ...
0
votes
3answers
207 views

Binary search algorithm in Clojure

I'm absolutely new to Clojure (started learning it yesterday). After I went through some tutorials and checked out the basics I implemented the following Binary search algorithm: ...
5
votes
3answers
3k views

Finding the root of a function by Bisection Method

The program has to look for a root in an interval [a,b]. The root should be declared with a certain accuracy eps. I.e it should ...
2
votes
2answers
169 views

Count of Smaller Numbers After Self

This is a LeetCode.com problem. https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/ You are given an integer array nums and you have to return a new counts array. The ...
3
votes
1answer
191 views

Iterative binary search

I have made a simple binary search algorithm with the assumptions that the input array is sorted and has only unique values. ...
1
vote
1answer
82 views

Binary search implementations comparison

I implemented a binary search algorithm. And did it using recursive and non-recurcive approaches. Then I compared the performance of both implementations with java out-of-the-box solution. And what I ...
2
votes
1answer
180 views

A binary search implementation for any datatype in C (continuation)

This is an indirect follow-up to this post. I've tried to assimilate all that was instructed and here's my attempt at binary search. binary_search.h ...
2
votes
0answers
236 views

Computing the square root of a number using binary search

This is implemented in MIPS assembly. I've hard-coded the initial guess, as I haven't figured out how to allow the user to input a negative or non-negative integer to then display the result back to ...
5
votes
2answers
1k views

Binary Search Tree in C++

I have written this code for Binary Search tree. Help me to improve this code using C++11 and C++14. Where to use functions like minimum() ...
4
votes
1answer
127 views

Binary search for a missing or default value by a given formula

An application I've been working on for a while needs a manner to find a missing element from a sorted array, the problem with the application is that these values aren't numeric. They have a formula, ...
5
votes
3answers
1k views
6
votes
2answers
539 views