How can I simplify this working Binary Search code in C?

by

There are a bunch of little things you have to get right in a binary search: handle the length=0 case, make sure the position you test is always valid, make sure you don’t overflow (i.e., `(low+high)/2′ is not the best way to write that), make sure the new test position is always different from the previous one, etc.

After having done it like a million times, every binary search I write is now done just like this:

bool search(int[] array, int length, int valueToFind)
{
    int pos=0;
    int limit=length;
    while(pos<limit)
    {
        int testpos = pos+((limit-pos)>>1);

        if (array[testpos]<valueToFind)
            pos=testpos+1;
        else
            limit=testpos;
    }
    return (pos < length && array[pos]==valueToFind);
}

Notice that we only need to do one comparison per iteration, which is faster than most implementations that can do 2. Instead of doing the equality test inside the loop, we reliably find the position where the element to find belongs, using only one comparison per iteration, and then at the end test to see if the element we want is there.

The way we calculate testpos ensures that pos <= testpos < limit, AND it works even if length is the largest possible integer value.

This form also makes it very easy to read off the invariants you want to see, without having to think about strange boundary conditions like high<low. When you come out of the loop, pos==limit so you don’t have to worry about using the wrong one, etc.

The condition in this loop is also easily adaptable to different-purpose binary searches like “find where to insert x, ensuring that it goes after all the xs that are already in the array”, “find the first x in the array”, “find the last x in the array”, etc.

More Related Contents:

  1. Pattern Programmings
  2. the problem is from a algorithm problem I do recently,but I can't gain the right answer [duplicate]
  3. Algorithm to find the smallest number in an array in C [closed]
  4. How to generate numbers upto 18 digits, sum of whose reciprocals is a whole number [closed]
  5. Finding target sum of two numbers in array
  6. How to remove blank spaces from buffer [closed]
  7. The most efficient way to implement an integer based power function pow(int, int)
  8. hash function for string
  9. Algorithm: efficient way to remove duplicate integers from an array
  10. Building a logarithm function in C without using float type
  11. Enumerate factors of a number directly in ascending order without sorting?
  12. Project Euler Question 14 (Collatz Problem)
  13. How do you print the EXACT value of a floating point number?
  14. Time complexity of a recursive algorithm
  15. How to find largest triangle in convex hull aside from brute force search
  16. C – How to implement Set data structure?
  17. Print all the permutations of a string in C
  18. Correctness of Sakamoto’s algorithm to find the day of week
  19. Why prefer start + (end – start) / 2 over (start + end) / 2 when calculating the middle of an array?
  20. find if 4 points on a plane form a rectangle?
  21. Generating a uniform distribution of INTEGERS in C
  22. Rolling median in C – Turlach implementation
  23. Rolling median algorithm in C
  24. Floating point linear interpolation
  25. Finding the intersecting node from two intersecting linked lists
  26. Finding out the duplicate element in an array
  27. Does C have any tools for doing string addition?
  28. Extend a line segment a specific distance
  29. QuickSort and Hoare Partition
  30. What is the difference between Linear search and Binary search?

Leave a Comment