# Questions tagged [binary-search]

Binary search is an efficient algorithm for finding an element in a sorted array. The basic idea is to cut the search space in half in each step. The complexity of the algorithm is O(log(n)).

1,806 questions
1answer
16 views

### Implemented Custom Binary search for 4 arguments but how to avoid the iteration to get lowerbound?

I am trying to implement custom binary search. I am clear on how to pass arguments and what to compare to get in which kind of sorted order but I want to avoid the iteration as I want to get lower ...
0answers
66 views

### Improving the time complexity of a function that returns the index of the first occurrence of an element in a list

UPDATE 1 (Oct.16): The original code had a few logic errors which were rectified. The updated code below should now produce the correct output for all lists L, S.T they meet the criteria for a special ...
2answers
29 views

### Function returns null if return is called within a conditional statement despite meeting the condition. Returns expected value outside of conditional

I am trying to write a simple script that performs a binary search on an array. If I try to call return inside one of the conditionals, the program successfully runs but it does not return anything. ...
2answers
49 views

### Indexed column and not indexed column research

I generated separate MySQL Innodb tables with 2000, 5000, 10000, 50000, 10000, 20000, 50000, 100 000, 200 000 elements(with help of php loop and insert query). Each table has two columns: id(Primary ...
2answers
76 views

### Binary search in lisp with higher level function

I am trying to write a (higher order function) which takes a vector and a function and makes a binary search accroding to that function, i.e. if it returns -1, we need to go lower, for 1 -- higher, ...
1answer
39 views

### Give a vector pair i have to find no. of pairs such that a number k is greater than first and smaller than second

number of i such that v[i].first<=k<=v[i].second in log(n) complexity
1answer
44 views

### Binary Search: Infinite Loop

I am trying to solve a binary search problem, however, I keep getting an infinite loop, since the values of lo hi and mid do not change as they suppose to. I am trying to search for a minimum mid ...
0answers
25 views

### Creating an array of increasing cost then inputting a year for results

I have been banging my head on the wall going through pages on the internet for hours now and I do not know where to begin on this homework assignment. I am very new to java and this one is just way ...
0answers
37 views

### counter to check if array X is subsequence of A not working (C)

I've tried following this program by hand, but I still can't get it to work. I have an array A = [4,3,2,1,4,3,2,1,4,3,2,1,4,3,2,1,4,3,2,1] and array X = [1,2,3]. I need to find the max number i for X^...
6answers
69 views

### Searching an array by value and index

I have a sorted array of integers, on which I want to perform searching. This array can have repeated values. If I search for an element that is repeated, then it should return the index of the first ...
0answers
26 views

### binary search counter not updating

I have two arrays, a fixed Array A and a dynamically updating array X. I am trying to find the max interleaving factor i for X^i, such that X^i is a subsequence of A. My X and A arrays are populating ...
1answer
34 views

### Use binary search to find interleaving sequence in C

I have two arrays, A and X, where A >= X. I want to find the max interleaving factor i for X^i such that X^i is a subsequence of A. For example, if A = [4,3,2,1,4,3,2,1,4,3,2,1,4,3,2,1], and X = [1,2,...
1answer
20 views

### For each element in the array find the number of ways to present it as a sum of two other numbers from this array

You are given the size of an array and the array itself. I know this problem can be solved effectively with the use of the binary search idea, but i don't know how to use it here. Would appreciate any ...
2answers
34 views

### why my javascript is showing value not founded?

I am trying to do a binary search in an array but my javascript is showing no value founded even when I entered a number that in the array in the prompt input var array = [10, 20, 30, 40, 50, 60,...
0answers
26 views

### Binary search for parallel array and testing it in a loop

So, I'm trying to conduct a binary search function to search the parallel array and then test it in a loop. I've been asked to prompt the user to enter a country code, such as CA then call the Binary ...
1answer
39 views

### Recursive binary search on a sorted array of Strings [closed]

I made an array that is 10 in length. Each slot has a name. My goal is to randomly pick a name and do a binary search to find it. I don't understand what is wrong with it but if you could at least ...
3answers
60 views

### Arrays.binarySearch not found [SOLVED] [duplicate]

int[] cost = {1, 4, 5, 3, 2}; int money = 4; int x = money / 2; int costIndex1 = Arrays.binarySearch(cost, x); System.out.println(x+" "+costIndex1 + " "+ cost[4]); x = 2 is not found ...
3answers
51 views

### C# Binary Search returning no result

CODE: using System; using System.IO; using System.Collections.Generic; class MainClass { public static void Main (string[] args) { Console.WriteLine ("Get Random Names"); // Read ...
0answers
35 views

### C# binary search always returns unhandled exception or no result… why? [duplicate]

Code: using System; using System.IO; using System.Collections.Generic; class MainClass { public static void Main (string[] args) { Console.WriteLine ("Get Random Names"); // Read ...
2answers
61 views

### While loop will not stop when using boolean variable?

I am trying to program a recursive binary search algorithm in python. However, I keep running into an infinite while-loop. I am afraid that it must be something simple that I am overlooking, but I ...
5answers
64 views

### Why binary search is returning -1 [duplicate]

I am working on a small program: public static void main( String args[]) { String[] places = {"Bangalore","Pune","San Francisco","New York City"}; Arrays.sort(places, new ...
1answer
32 views

### Regex Match Hexidecimal in Groups of 2-8

I am working on a regular expression to match against a hexadecimal string and having some trouble near the end. I am specifically looking for groups of 2 bytes that do not contain 00 that are between ...
0answers
25 views

### How to do interleaving sequence in C coding (Simplest way)?

Providing the following code as an attempt to do interleaving sequence: int interleave (int *a, int *x, int num, int num2) { int i,j,in,x2[num]; printf("What would be the mid number?\n"); scanf("%d", ...
4answers
55 views

### Group what is between null bytes using Regex on FileStream

I am going through a binary file and need to group some bytes that are between null values so I can do some int.Parse() conversions, Given the following bytes, how would you get back the groups: C8 ...
2answers
17 views

### Comparing leaf nodes of binary search and merge sort

For binary search, it forms a complete binary tree, so n = (2^k)-1. 2-way merge sort also forms a complete binary tree but n = 2^k, why is this? Why is it not also (2^k) -1?
1answer
32 views

### Binary search in a list which contains 2 sorted sections

I know that binary search only works in a sorted list. I want to search ( O(log n) ) and be able to find an item in a list with 2 sorted sections. EX: [20,30,1,2,3,4,5] Is O(log n) binary ...
1answer
35 views

### Custom Newline in Binary Stream using Hex Array in WPF

I have a binary file I am reading and printing into a textbox while wrapping at a set point, but it is wrapping at places it shouldn't be. I want to ignore all line feed characters except those I have ...
2answers
48 views

### Search array for a similar / most similar string Java

I am working on a project where I have book names in an XML file. These are then parsed and turned into an array list of book objects. Now I want to search through them. I have already successfully ...
1answer
19 views

### Dictionary graph to list by breadth-first order

I have the following graph (which is in this case is a binary tree) as a dictionary. G = { 'root': ['4', '3'], '4': ['2', 'a'], '3': ['1', 'd'], '2': ['b', 'e'], '1': ['f', 'c'] ...
2answers
60 views

### Create a guessing game, where the computer guesses the number that the user inputs

Given that user input should be between 1 and 1000, I'm trying to use a binary search of a (sorted) integer array of 1-1000 to output the following: enter image description here I just want the ...
1answer
21 views

### given array with n numbers such that arr[0] is even and arr[n-1] is odd, find index i such that a[i] is even and a[i+1] is odd

Suppose I have an array A with n numbers, so that the first element of this array is even, and last one is odd- I would like to write an function which find index i , such that A[i] is even and A[i+...
2answers
80 views

### How can I perform a binary search on a list of objects in Scala

case class Employee (id: Int, name : String, age : Int) // Added four emplyees emp1, emp2 emp3, emp4 to the list like below:: val emp1 = Employee(101, "name1", 101) val emp2 = Employee(102, "name2", ...
5answers
105 views

### Binary search for square root 2

I have an issue where my binary search algorithm to find the square root of 2 appears to be in an infinite loop and runs forever: num = 2 low = 1 high = num i = 0 while((i**2) != 2): #was while(low&...
1answer
82 views

### recursive binary search in ruby

I've been learning some algorithms and I can't find the reason why my method is failing. if you could look at the code and shed some light as to why that is happening. I would truly appreciate it. I'...
1answer
58 views

### How do I make a variable array size?

So my program is functional. I just want it to use a binary search of a text file and determine the highest index number it can be found in. If it cannot be found it finds the next largest and makes ...
4answers
96 views

### Why is return executed twice

In this case the value does match and the value of boolean is set to true,however return is called twice and does update the value to false.Can anyone suggest what am I missing here?. public class ...
3answers
108 views

### Index was out of range after deleting multiple rows from the datagridview? C#

I use an ArrayList for my binary search. The datagridview's rows is added to the ArryList. When I deleting a single row from the datagridview, it works almost perfectly. The problem is when I delete ...
3answers
83 views

### Why is there still an error case in this binary search of sorted array scenario?

For the record, I came across this question on some web coding site, but I am really interested in what I missed rather than scores. Here it goes: Implement function countNumbers that accepts a ...
1answer
39 views

### Parsing binary search as an arraylist in C#

Is there any possible way to make this code shorter? int? index = ListOfPeople.BinarySearch(searchBar.Text); int? temp = int.TryParse(index.ToString(), out int i) ? (int?)1 : ...
0answers
26 views

### Function returning None Instead of a value in Binary Search using Recursion [duplicate]

I have read answers like python recursive function returning none instead of string and Recursive code returns None But i am not able to get it where should I place this :- You probably want a ...
4answers
51 views

### Binary search function not working

I'm new to Java and am just beginning to learn some simple data structures and algorithms. I've been trying to implement a binary search function but I keep getting a stack overflow error and I don't ...
2answers
125 views

### Binary search for first occurrence in a dictionary list

So I am dealing with large datasets, n>1000000. The data contains order information about an item. There is a boolean within the JSON formatted order called is_buy_order. I would like to split the ...
1answer
88 views

### Can this be done in O(logN) complexity?

You are working on a project and you noticed that there has been a performance decrease between two releases. You have a function: boolean worseCommit(int commit1, int commit2) that runs ...
1answer
29 views

### Learning Binary Search in python 3.7

I found this code on https://www.geeksforgeeks.org/binary-search/ # Python Program for recursive binary search. # Returns index of x in arr if present, else -1 def binarySearch (arr, l, r, x): #...
2answers
44 views

### How to search for anagrams in O(logN) time given an input from the user?

Hi I've been thinking of how to implement this for days. I'm trying to implement a programme that reads a dictionary into a list and sorts it in O(N) time.After that, I have to search for the ...
3answers
76 views

### Longest sequence with given color

Suppose we have a list of elements with values in Black and White. Is there an O(N) algorithm to find the longest sequence comprising of black elements? I know that using binary search we can do at ...
1answer
35 views

### Given an input string how to search for all the anagrams in O(k logN + W) time where W is the output size and k is the max characters in the string?

I am trying to write a program that given an input string by the user finds all anagrams available in a list? The O(klogN + W ) time complexity does not include time complexity for sorting. My ...
2answers
50 views

### Binary search for integer64 in data.table

I have a integer64 indexed data.table object: library(data.table) library(bit64) some_data = as.integer64(c(1514772184120000026, 1514772184120000068, 1514772184120000042, 1514772184120000078,...
2answers
66 views

### Intuition behind this solution

I am trying to solve a question on LeetCode.com: A positive integer is magical if it is divisible by either A or B. Return the N-th magical number. Since the answer may be very large, return it ...
1answer
49 views

### Can uppper_bound be expressed in terms of lower_bound

For a array can i calculate the upper_bound of a number in array using its lower_bound always. For ex we are given an array: 2 3 4 4 4 5 6 we are to find upper_bound of 4 which is at index 5 (2 is ...