20.二分查找

待我称王封你为后i 2022-02-14 08:01 131阅读 0赞

1.分清指针的边界值意义，采用两种不同的边界值指针进行二分搜索

二分查找适合有序数组的查找，每次与数组的中间元素对比，小的话，左半部分查找，大的话右半部分查找

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NsNzIzNDAx_size_16_color_FFFFFF_t_70][]

public class BinarySearch<T extends Comparable> {
        /**
         * 二分查找
         * @param arr
         * @param n
         * @param target
         * @return
         */
        public int binarySearchTarget(T arr[],int n,T target){
            int l=0,r=n-1;//边界设置，[l……r]的范围里找target
            while(l<=r){//l==r,[l……l]依然有效
                int mid=l+(r-l)/2;
                if(arr[mid].compareTo(target)==0)
                    return mid;
                else if(target.compareTo(arr[mid])>0){
                    l=mid+1;//[mid+1,r]
                }
                else
                    r=mid-1;//[l,mid-1]
            }
            return -1;
        }
        public int binarySearchTarget2(T arr[],int n,T target){
            int l=0,r=n;//边界设置，[l……r)的范围里找target
            while(l<r){//l==r,[l……l)无效，[42,43)
                int mid=l+(r-l)/2;
                if(arr[mid].compareTo(target)==0)
                    return mid;
                else if(target.compareTo(arr[mid])>0){
                    l=mid+1;//[mid+1...r)
                }
                else
                    r=mid;//[l,mid)
            }
            return -1;
        }
    
        public static void main(String[] args) {
            int n = new BinarySearch<Integer>().binarySearchTarget(new Integer[]{1,3,4,5,8},5,1);
            System.out.println(n);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NsNzIzNDAx_size_16_color_FFFFFF_t_70]: /images/20220214/765b666c7bd3454d965249e4f1e590c8.png