There is an implementation of the binary search algorithm. Why is there a bit shift and ref in the parameters?

public static int binarySearch(ref int[] x, int searchValue, int left, int right) { if (right < left) { return -1; } int mid = (left + right) >> 1; if (searchValue > x[mid]) { return binarySearch(ref x, searchValue, mid + 1, right); } else if (searchValue < x[mid]) { return binarySearch(ref x, searchValue, left, mid - 1); } else { return mid; } }

    2 answers 2

    (right + left) >> 1 is the same as (right + left) / 2 since in the general case

    a >> x == a / 2^x

    you have x = 1 so dividing by 2 obtained. ref in parameters, in this case it’s not necessary and unnecessary, since arrays in many languages ​​are always passed by reference (or by pointer as in pluses)

      A bit shift in this case is equivalent to dividing by two. In general, the ref link is needed so that the parameter is passed by reference. But there are two "but":

      1. In Sharpe, the array is passed by reference.
      2. The array method does not change.

      After reading msdn, I thought that maybe this is used so that the method for the uninitialized array cannot be called.

      • It is impossible to call it without a noninitialized call :) - Pavel Mayorov