Binary search the specified number of numbers in the array binary advanced

Use binary search to count the number of the same number as the target number in the array

The idea of the algorithm is based on the binary search number , The purpose is to count how many numbers in the array are equal to the target number .

notes ：

• When used directly for Loop through the array , Each iteration is compared once , The time complexity will be O(n)
• If you use a binary search , First find a subscript equal to the target number , Use while Centered around this subscript , Compare left or right . If the same number is only 2 If you want to , Then search left and right once and you will get the result , But if all the numbers in an array are the same , Then we still need to compare n Time , The time complexity of searching according to this idea is also O(n).
• The idea I use here is First use a binary search to find the left boundary of this number , Then, when the left boundary is found, the right boundary of the number is found by using a bisection search , The difference between the right bound and the left bound is the number of this number in the array . The time complexity of this algorithm is the same as that of the general bisection algorithm . All are O(lgN).

import java.util.Scanner;

public class BinarySearch_findSameNum {
    
    public static void main(String[] args) {
    
        int arr[] = {
    1, 1, 5, 5, 5, 8, 8, 9, 10, 15, 15};        // Define an ordered binary array 
        int target = new Scanner(System.in).nextInt();           // Enter the number of lookups 
        left(arr, 0, arr.length, target);                   // The first two points   Find the left boundary 
    }

    // Find the function of the left boundary left
    private static void left(int[] arr, int low, int high, int target) {
    
        while (low <= high) {
        // Definition while The end condition of the loop   When subscript low>high Jump out when while loop 
            int middle = (low + high) / 2;// Be careful   there middle The way of calculation will have a great impact   I still use the method of adding to get the median 
            if (arr[middle] >= target) {
    
                // Here we need to find the left boundary , So when arr[middle] Greater than or equal to target when , Then it is proved that the left boundary is low~middle-1 Between 
                // Be careful   When looking for a number in two , When arr[middle]==target You will find the result you want to find , But this is not the end .
                //  Because the target number in the array has 2 Or 2 More than one time , The index found is probably not the leftmost one , You also need to cycle , Until you find the left boundary 
                high = middle - 1;  // Change superscript , Continue traversing 
            } else {
    
                low = middle + 1;
            }
        }// When constantly while When traversing a loop ,low The value of must be greater than high

        // The subscript that determines the end of the last loop low Whether the corresponding array value is the same as target equal 
        if (arr[low] == target && low < arr.length) {
    
            System.out.println("left search success:" + low);

            // equal , Then the left boundary exists . First obtain the left boundary of the target number low
            int right = right(arr, low+1, arr.length - 1, target);  // Looking for a bounded function in a call right
            // Be careful   The subscript and superscript passed to the right boundary function here are different from those when finding the left boundary   Because we have found the left boundary , All the data on the right side of the left boundary of the array can be directly passed to the function 
            // The subscript can take low+1
            // The superscript here is arr.length - 1  The length of the array minus 1 ！！！！ This -1 It's very important , Corresponding middle Calculation method of .
            // Because I add and divide superscript and subscript directly 2 Of   Take this topic for example . Find the function to find the right boundary . To find 15  When the left boundary is found 9 when   Then superscript 11 Transfer the past  middle Calculated 10
            // arr[10]=15 Exactly equal to target, At this point, the subscript low Add 1.low=11 After that, the array will be out of bounds   So will arr.length-1 Transfer the past   Superscript 10, There will be no subscript +1 Post crossing 
            System.out.println(" Array with " + target + " The same is ：" + (right - low + 1) + " individual ");
        } else {
    
            System.out.println("error");
        }
    }

    // Find the function of the right boundary right
    private static int right(int[] arr, int low, int high, int target) {
    
        // It's easy to find the right boundary , The idea is the same as finding the left boundary 
        while (low <= high) {
    
            int middle = (high + low) / 2;
            if (arr[middle] <= target) {
    
                // If arr[middle] <= target  Just keep changing the value of the subscript , until low>high Jump out of while loop 
                low = middle + 1;
            } else {
    
                high = middle - 1;
            }
        }
        if (arr[high] == target && high < arr.length) {
    
            System.out.println("right search find:" + high);
            return high;  // Returns the index of the right boundary 
        } 
    }
}

I wrote it in my spare time , If there are mistakes, please correct them