This is the 16th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

What is binary search?

Binary search refers to an ordered set of data. Each time, the range to be searched is reduced by half by comparing with the elements in the middle of the range, until the element to be searched is found, or the range is reduced to 0.

Time complexity analysis?

  1. Time complexity

    Let’s say the data size is n, and the data shrinks by half after each search, and in the worst case, it doesn’t stop until the search interval shrinks to empty. So, the data size of each search is: n, n/2, N /4… , n / 2 ^ (k),… This is a geometric sequence. When n over 2 to the k is equal to 1, the value of k is the total number of pinches, the total number of lookups. Each reduction operation only involves the size comparison of two data. Therefore, after k interval reduction operations, the time complexity is O(k). If n/(2^k)=1, we get k=log base 2n, so the time is order log base n.

  2. O (logn)

    1. This is an extremely efficient time complexity, sometimes even more efficient than the O(1) algorithm. Why is that?
    2. Because logn is a very scary order of magnitude, even if n is very large, logn is very small. For example, n is equal to 2 to the 32nd, which is 4.2 billion, and logn is only 32.
    3. So, O(logn) is sometimes a lot faster than O(1000), O(10000).

Three, how to achieve binary search?

Cycle to achieve

PHP code implementation:

    // The loop implements binary search
    public function bsearchLoop(array $array.int $n.$value)
    {
        $low = 0;
        $high = $n - 1;
        while ($low< =$low) {
            $mid = $low + (($high - $low) > >1);
            if ($array[$mid] > $value) {
                $high = $mid - 1;
            } elseif ($array[$mid] < $value) {
                $low = $mid + 1;
            } else {
                return $mid; }}return -1;
    }
Copy the code

Matters needing attention:

  1. The loop exit conditions are:low<=highRather thanlow<high.
  2. The value of mid is usedmid=low + (high - low) / 2Instead,mid=(low + high)/2Because if low and high are large, the sum might occurintThe value of the type exceeds the maximum range. To maximize performance, divide by 2 can be converted to a bitwise operation, i.elow + ((high - low) >> 1)Because computers can process bit operations much faster than division.
  1. Update to low and end:low = mid - 1.high = mid + 1, if you write it aslow = mid.high=mid, an endless loop may occur.

The recursive implementation

    // Recursive binary search
    public function bsearchRecursion(array $array.int $n.$value)
    {
        return $this->bSear($array.$value.0.$n - 1);
    }

    private function bSear(array $array.$value.int $low.int $high)
    {
        if ($low > $high) {
            return -1;
        }
        $mid = $low + (($high - $low) > >2);
        if ($array[$mid] = =$value) {
            return $mid;
        } elseif ($array[$mid] > $value) {
            $high = $mid - 1;
        } else {
            $low = $mid + 1;
        }
        return $this->bSear($array.$value.$low.$high);
    }
Copy the code

4. Conditions of use (limitations of application scenarios)

  1. Binary lookup relies on sequential table structures, known as arrays.
  2. Binary search is for ordered data, so it can only be used in scenarios where insertion and deletion operations are infrequent and multiple searches are sorted at one time.
  3. The amount of data is too small for binary search, and the efficiency is not significantly improved compared with direct traversal. There is one exception, however, that is the comparison between data is very time-consuming, such as the array is stored in the length of more than 300 strings, so it is better to minimize the comparison operation and use binary lookup.
  4. Binary lookup is also not a good idea because arrays require contiguous space, and if you have too much data, you often can’t find contiguous memory space to store such large amounts of data.

5. Recursive variants

1. Find the element whose first value equals the given value

    1. Find the element whose first value is equal to the given value
    public function bsearch1($array.int $n.$value)
    {
        $low = 0;
        $high = $n - 1;
        while ($low< =$high) {
            $mid = $low + (($high - $low) > >1);
            if ($array[$mid] > $value) {
                $high = $mid - 1;
            } elseif ($array[$mid] < $value) {
                $low = $mid + 1;
            } else {
                if ($mid= =0 || $array[$mid - 1] != $value) {
                    return $mid;
                } else {
                    $high = $mid - 1; }}}return -1;
    }
Copy the code

2. Find the element whose last value equals the given value

    // Variant 2. Find the element whose last value is equal to the given value
    public function bsearch2(array $array.int $n.$value)
    {
        $low = 0;
        $high = $n - 1;
        while ($low< =$high) {
            $mid = $low + (($high - $low) > >1);
            if ($array[$mid] > $value) {
                $high = $mid - 1;
            } elseif ($array[$mid] < $value) {
                $low = $mid + 1;
            } else {
                if ($mid= =$n - 1 || $array[$mid + 1] != $value) {
                    return $mid;
                } else {
                    $low = $mid + 1; }}}return -1;
    }
Copy the code

3. Find the first element that is greater than or equal to the given value

    // variant 3. Find the first element greater than or equal to the given value
    public function bsearch3(array $array.int $n.$value)
    {
        $low = 0;
        $high = $n - 1;
        while ($low< =$high) {
            $mid = $low + (($high - $low) > >1);
            if ($array[$mid] > =$value) {
                if ($mid= =0 || $array[$mid - 1] < $value) {
                    return $mid;
                } else {
                    $high = $mid - 1; }}else {
                $low = $mid + 1; }}return -1;
    }
Copy the code

4. Find the last element whose value is less than or equal to the given value

    Find the last element that is less than or equal to the given value
    public function bsearch4(array $array.int $n.$value)
    {
        $low = 0;
        $high = $n - 1;
        while ($low< =$high) {
            $mid = $low + (($high - $low) > >1);
            if ($array[$mid] > $value) {
                $high = $mid - 1;
            } else {
                if ($mid= =$n - 1 || $array[$mid + 1] > $value) {
                    return $mid;
                } else {
                    $low = $mid + 1; }}}return -1;
    }
Copy the code