# Questions tagged [binary-search]

Questions about the binary search algorithm, which can be used to find elements of an ordered list in O(log n) time.

93 questions
Filter by
Sorted by
Tagged with
46 views

### Worst case runtime for binary search

The run time of binary search is O(log(n)). log(8) = 3 It takes 3 comparisons to decide if an array of 8 elements contains a given element. It takes 4 comparisons in the example below. python2.7 <...
46 views

### Is there an O(n) solution for this problem?

I have found this problem on CodeForces.The problem is in the following link: https://codeforces.com/problemset/problem/729/C Problem Starts here: Vasya is currently at a car rental service, and he ...
43 views

### Find $n'th$ perfect number , where perfect number is a positive integer whose sum of digits is $10$

For example $46$ is a perfect number , since $4+6=10$ . If $n=1$ , answer is $19$. If $n=2$ , answer is $28$. If $n=3$ , answer is $37$ and so on .We need to make a program which takes $n$ and ...
12 views

### What is the work complexity for optimal merge using partitioning of sorted array of size n and p processors with segments of size n/p?

Using optimal method to find rank, we can partition a sorted array(size n) in segments of size n/p using p processors. The, we can find the rank of an element by placing a processor at the start and ...
22 views

### Intersection of 2 arrays

Here is a question i came across : Given two arrays, write a function to compute their intersection.Here we will allow the duplicates. Note: Each element in the result should appear as many ...
50 views

### Dividing 2 integers with some constraints

This a problem i came across while practicing binary search. Here is the problem: Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. ...
100 views

### Is there a O(log n)-time algorithm to find the maximum element of a circular shift of a sorted array?

Consider this problem: You are given an array $A$ (of distinct integers) of one out of the following four types: Ascending (e.g., 1,2,4,6); Descending (e.g., 6,4,2,1); Ascending rotated (a non-...
27 views

### Understanding the behaviour of different variations of Binary Search

Binary Search is a fairly simple and standard algorithm that can be used (among other things) to find a target element in a sorted array. There are subtle variations in code to do this, however all of ...
34 views

### time complexity of 2 sum problem using binary search

this is a popular searching problem and the question is : Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The ...
30 views

### number of comparisons in searching algorithms

i was going thorugh different searching algorithms,Linear,binary and ternary search.Now i want to know the number of comparisons in these. For linear search : ...
35 views

### Finding the rightmost element in an array of duplicate elements using binary search

i was reading Binary Search in the wikipedia and i came across this part of 'rightmost index of an element in an array of duplicate elements'. i understood the process of determining the leftmost ...
29 views

### Smallest segment after whose removal all elements are distinct

I am interested in the following problem: We are given an array of integers and we need to find the size of smallest subsegment such that after removing it all elements in the array are distinct. ...
39 views

### Extend binary search

There is a way for finding K entries of N given entries using a binary search? I mean, I have N entries that indexed from 0 to N-1 and I have to find K of them that answer some condition. The naive ...
21 views

### Linearithmic solution to finding closest pairs in an array of N elements

I am reading Algorithms 4ed by Sedgewick and Wayne. I came across this algorithm design question that asks the following: Write a program that given an array of N integers, finds a closest pair: two ...
77 views

### Binary search uneven split number of queries?

For even split binary search (repeated halving) number of queries is log with base 2. According to Skiena's Algorithm Design Manual, if the split in binary search is by ratio 1/3:2/3 instead of 1/2:1/...
65 views

### Finding $k$-th element in prefix of size $i$

Let's say we are given array $A$ of size $n$. We need to answer some numbers of queries. For each query we are given index $i$ and integer value $k$, $k \le i$. If we take the first $i$ elements of ...
22 views

1k views

### How do I find maximum and minimum number of times the search loop will execute when searching through an array of 1,048,576 integers

I have tried to calculate the maximum number of times the loop will search through this large array, but I am not sure if I have that correct and I also need help with or pointers of how I can ...
1k views

### Why is binary search using this weird thing to calculate middle?

I noticed that in many books calculation of midpoint for binary search uses this: int mid = left + (right - left) / 2; Why not use ...