Finding multiple entries with binary search

by

Well, as the list is sorted, all the entries you are interested in are contiguous. This means you need to find the first item equal to the found item, looking backwards from the index which was produced by the binary search. And the same about last item.

You can simply go backwards from the found index, but this way the solution may be as slow as O(n) if there are a lot of items equal to the found one. So you should better use exponential search: double your jumps as you find more equal items. This way your whole search is still O(log n).

More Related Contents:

  1. Find kth smallest element in a binary search tree in Optimum way
  2. how to calculate binary search complexity
  3. Binary Search in Array
  4. Calculating mid in binary search
  5. Which is faster, Hash lookup or Binary search?
  6. What are the pitfalls in implementing binary search? [closed]
  7. What is the difference between Linear search and Binary search?
  8. How to apply binary search O(log n) on a sorted linked list?
  9. Priority scoring algorithm [closed]
  10. Efficient way to add element to sorted datastructure [closed]
  11. How to count the number of set bits in a 32-bit integer?
  12. Algorithm to return all combinations of k elements from n
  13. Graph Algorithm To Find All Connections Between Two Arbitrary Vertices
  14. Choosing n numbers with fixed sum
  15. Algorithm to randomly generate an aesthetically-pleasing color palette [closed]
  16. What is a good Hash Function?
  17. The Sieve of Atkin
  18. How to calculate the entropy of a file?
  19. Longest acyclic path in a directed unweighted graph
  20. 3 dimensional bin packing algorithms
  21. Finding the best trade-off point on a curve
  22. Find cycle of shortest length in a directed graph with positive weights
  23. Random points inside a parallelogram
  24. How is 2D bin packing achieved programmatically?
  25. Optimizing Conway’s ‘Game of Life’
  26. Why increase pointer by two while finding loop in linked list, why not 3,4,5?
  27. How do I find the median of numbers in linear time using heaps?
  28. Finding rectangles in a 2d block grid
  29. Check if array B is a permutation of A
  30. Algorithm to list all unique permutations of numbers contain duplicates

Leave a Comment