Massive Algorithms: A Problem in Many Binary Search Implementations

int binarySearch(int arr[], int l, int r, int x)

{

    while (l <= r)

{

        // find index of middle element

        int m = (l+r)/2; // may overflow: during code interview, extract this as method

        // Check if x is present at mid

        if (arr[m] == x) return m;

        // If x greater, ignore left half

        if (arr[m] < x) l = m + 1;

        // If x is smaller, ignore right half

        else r = m - 1;

}

    // if we reach here, then element was not present

    return -1;

}

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

Probably faster, and arguably as clear is (works only in Java, refer this):

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

Labels