Calculating mid in binary search

by

This post covers this famous bug in a lot of detail. As others have said it’s an overflow issue. The fix recommended on the link is as follows:

int mid = low + ((high - low) / 2);

// Alternatively
int mid = (low + high) >>> 1;

It is also probably worth mentioning that in case negative indices are allowed, or perhaps it’s not even an array that’s being searched (for example, searching for a value in some integer range satisfying some condition), the code above may not be correct as well. In this case, something as ugly as

(low < 0 && high > 0) ? (low + high) / 2 : low + (high - low) / 2

may be necessary. One good example is searching for the median in an unsorted array without modifying it or using additional space by simply performing a binary search on the whole Integer.MIN_VALUE–Integer.MAX_VALUE range.

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. Finding multiple entries with 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. How do I search for a number in a 2d array sorted left to right and top to bottom?
  10. Generate an integer that is not among four billion given ones
  11. How to generate Sudoku boards with unique solutions
  12. Time complexity of Euclid’s Algorithm
  13. Quick sort Worst case
  14. How to round floats to integers while preserving their sum?
  15. Modulus power of big numbers
  16. How can I detect common substrings in a list of strings
  17. Algorithm to list unique permutations of string with duplicate letters
  18. What algorithm to use to determine minimum number of actions required to get the system to “Zero” state?
  19. Collision detection of huge number of circles
  20. The sieve of Eratosthenes in F#
  21. Fuzzy date algorithm
  22. Most efficient way to calculate Levenshtein distance
  23. reconstructing a tree from its preorder and postorder lists
  24. Why do we ignore co-efficients in Big O notation?
  25. Previous power of 2
  26. Randomly choosing from a list with weighted probabilities
  27. Planar Graph Layouts
  28. how to determine if the kth largest element of the heap is greater than x
  29. Do iterative and recursive versions of an algorithm have the same time complexity?
  30. Complete graph with only two possible costs. What’s the shortest path’s cost from 0 to N – 1

Leave a Comment