### ymrg3307's blog

By ymrg3307, history, 3 years ago,

Why my problem going time limit exceeded even I am implementing binary search my solution

• 0

 » 3 years ago, # |   0 Your solution uses Array.LastIndexOf. This Java function iterates over the complete array, so the complexity will again be O(n). Look with the binary search for the smallest element a[i] that is greater than x, then the answer is i.
•  » » 16 months ago, # ^ |   0 I am sorting then using binary Search but it is still giving TLE. Can you check this one and let me know why?63616723
•  » » » 16 months ago, # ^ |   0 Your binary search implementation is wrong. The idea behind binary search is, that the search range gets halved each time. In your implementation you decrease the search range only by one (via left++ and right--), so the complexity is as bad as just doing a linear search.For a binary search you need something like left = mid + 1 instead of left++ and right = mid-1 instead of right--. But no guarantee, that this is the only mistake. I only glanced over your code for a second.
•  » » » » 16 months ago, # ^ |   0 Btw, that's also a very long way of writing the binary search.I would write it like that: int l = -1; int r = list.size(); while (l + 1 < r) { int m = l + (r - l) / 2; if (list.get(m) >= k) l = m; else r = m; } return l + 1; The idea behind my though process is: I sustain two invariants the complete program. l is the largest shop that I know of in which I can buy the candy. At the beginning I don't even know if I can buy it at the first shop, so I initialize it with l = -1. r is the smallest shop where I know that I can't buy the candy, so at the beginning it is list.size(), since I don't know if I can buy from the last one or not.
•  » » » » » 9 months ago, # ^ |   0 I want to know, how we could have done this problem if prices at some shops would be same?
•  » » » » » » 9 months ago, # ^ |   0 Exactly the same way.
•  » » » » » » » 9 months ago, # ^ |   0 But we also have to keep track of the frequency of prices ?
•  » » » » » » » » 9 months ago, # ^ |   0 No, that doesn't matter.I wrote that in my code I find the largest shop that I know of in which I can buy the candy. This is maybe a little imprecise. Correctly it should be: I find the largest index such that I can buy from the shop corresponding to the index.And that handles duplicates per default. E.g. if the prices are $2, 3, 5, 5, 6$ and I have $5$ coins. Then I find the index 3. prices: 2, 3, 5, 5, 6 indices: 0, 1, 2, 3, 4 ^ 
•  » » » » » » » » » 9 months ago, # ^ |   0 Thanks for the explanation ,I understood it
•  » » » » 16 months ago, # ^ |   0 Actually I woke up today realizing i wrote that wrong lmao. Sorry, my bad. Thanks for checking it out!
 » 3 years ago, # | ← Rev. 2 →   0 The following is a simple C++17 implementation using upper_bound function. 37844068
 » 6 weeks ago, # | ← Rev. 3 →   -12 In your binary search implementation, if x equals to arr[mid] then you are using LastIndexOf (which has O(n) complexity) that's why you are getting TLE I recently solved this problem and I faced the same problem you need to replace LastIndexOf with binary search which finds the last occurrence of any element like this one. public static int binarySearchFindLastOccurence(int[] arr, int target) { int mid, right = arr.length-1, left = 0; int endIdx = -1; while (left <= right) { mid = left + (right-left) / 2; if(arr[mid] > target) { right = mid-1; } if(arr[mid] <= target) { if(arr[mid] == target) endIdx = Math.max(endIdx, mid); left = mid + 1; } } return endIdx; } Please don't copy the code try to understand it. Here is my solution for further reference Solution
•  » » 6 weeks ago, # ^ |   0 come on man, its a 3 year old post.
•  » » » 6 weeks ago, # ^ |   0 Oh shit