3,027 questions
0
votes
1
answer
86
views
Why is the worst-case binary selection sort time complexity considered O(n^2)?
Wikipedia and other textbooks reference binary selection sort's asymptotic worst-case time complexity to be O(n^2), usually justifying this with any extra computation caused by swaps. I don't ...
- 23
3
votes
1
answer
188
views
Where is the flaw in this greedy approach?
I am sitting on a LeetCode problem, specifically Minimum Time to Repair Cars.
You get a list of how many mechanics you have and how many cars you need to fix.
Each mechanic has a rank, and he takes ...
- 77
-1
votes
1
answer
170
views
Why does my binary search return -1 even if the element exists? [closed]
I'm trying to implement a binary search in Java to find the index of a target value in a sorted array.
But even when the element exists, my function returns -1.
Code:
public int binarySearch(int[] arr,...
- 23
-3
votes
1
answer
110
views
Trouble finding peak in mountain-like array with duplicates — binary search not working as expected [closed]
I’m trying to solve a problem where I need to find the peak element in a mountain-like array that may contain duplicates.
A peak element is one where the values first increase and then decrease (but ...
0
votes
1
answer
94
views
BinarySearch method on array sorted In descending order with no exact match [duplicate]
If I have an array of values in ascending order and use the Array.BinarySearch, then if the sought after value doesn't actually exist, BinarySearch will return the index of the first highest value in ...
- 468
8
votes
1
answer
209
views
Given an array of numbers including positive and negative, how to find the shortest subarray that has a sum >= target using prefixSum and bisect?
During a coding challenge I encountered a variation of Leetcode 209. Minimum Size Subarray Sum, where the array contains not only positive numbers but negative ones, in which case, sliding window ...
- 2,659
-2
votes
1
answer
132
views
Constrained MST: Find a spanning tree of weight ≤ T that minimizes the number of red edges
We are given an undirected graph ( G = (V, E) ), where:
( V ) is the set of vertices (or nodes),
( E ) is the set of edges.
Each edge ( e ∈ E ) has two attributes:
A weight ( w(e) ), which is a ...
- 103
0
votes
1
answer
99
views
Clojure mutant – can't kill a surviving mutant in binary search
I'm writing a classic binary search function in Clojure and testing it with the mutant mutation testing library.
My tests work fine in terms of correctness, but mutation testing reports one surviving ...
0
votes
2
answers
86
views
Find start index of a rotated non-decreasing array
This is part of a interview question I recently came across and Im not able to find an elegant solution for this. Can someone please help.
Q - We have a non-decreasing sorted array, which is rotated ...
- 127
-2
votes
3
answers
122
views
How to do binary search correctly [closed]
I am trying to solve this question on Leetcode:
74. Search a 2D Matrix
You are given an m x n integer matrix matrix with the following two properties:
Each row is sorted in non-decreasing order.
The ...
- 13
-3
votes
2
answers
89
views
Binarysearch with Python with recursion
def binarysearch(a,n):
mid=int(len(a)/2) #taking the middle point
if(n==a[mid]):
return mid
elif(n>a[mid]): #if greater then do binarysearch in smaller part
binarysearch(a[(mid+1):],n)
...
- 109
0
votes
0
answers
44
views
Finding an element in the matrix with a least amount of steps
I have a W x H matrix, random starting position x0,y0, and the target with unknown coordinates. On every step I get information of direction to the target (above-below, left-right) and then have to ...
1
vote
2
answers
71
views
What is the idiomatic way to handle code duplication in match bindings for Result? [duplicate]
I'll give some context here. The closure foo takes in a character and inserts it into a sorted vector. foo uses binary_search_by_key to insert the character into the vector at the correct index.
What ...
- 2,322
0
votes
0
answers
62
views
Generic binary search Java with Comparator and Comparable [duplicate]
I'm being asked to create a binary search that can use either Comparable or Comparator depending on which constructor is being used. I made a private boolean to note whether or not to use the object's ...
- 19
1
vote
1
answer
61
views
When are bisect_left(arr, x) and bisect_right(arr, x-1) equal?
If you are doing this on a sorted array arr then would bisect_left(arr, x) == bisect_right(arr, x-1) under any circumstances?
- 11