BinarySearch

傷城~ 2021-10-01 11:14 248阅读 0赞

# 前提 #

必须是有序数组。

# 思路 #

![18721752-adb1807eea343693.png][]

image.png

# 无重复数组二分查找 #

# 有重复数组二分查找 #

## 思路 ##

1.退出条件  
leftIndx>rightIndex  
2.中值比较  
如果相等，先不退出，因为前提是有序数组，找其左右是否也有相同值，直到左右都不等于targetValue  
3.二分递归

package com.pl.arithmetic.search;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * <p>
     *
     * @Description: TODO
     * </p>
     * @ClassName BinarySearch
     * @Author pl
     * @Date 2020/12/20
     * @Version V1.0.0
     */
    public class BinarySearch {
    
        public static void main(String[] args) {
            int arr[] = { 1, 8, 10, 89,1000,1000,1000, 1234 };
           // int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 , 11, 12, 13,14,15,16,17,18,19,20 };
            //
        /*  int resIndex = binarySearch(arr, 0, arr.length - 1, 11);
            System.out.println("resIndex=" + resIndex);*/
    
            List<Integer> resIndexList = binarySearchPlus(arr, 0, arr.length - 1, 1000);
            System.out.println("resIndexList=" + resIndexList);
        }
    
    
        public static int binarySearch(int[] arr,int leftIndex,int rightIndex,int targetValue){
            //todo 先判断是否需要查找
            if (leftIndex>rightIndex){
                return -1;
            }
            //todo 中指比较,递归查找
            int midIndex =  (leftIndex+rightIndex)/2;
            int midValue = arr[midIndex];
            if (midValue == targetValue){
                return midIndex;
            }
            //和midValue比较，如果小于midValue，左递归，反之右递归
            if (midValue>targetValue){
                return binarySearch(arr,0, midIndex-1,targetValue);
            }else {
                return binarySearch(arr,midIndex+1,rightIndex,targetValue);
            }
        }
    
        //完成一个课后思考题:
        /*
         * 课后思考题： {1,8, 10, 89, 1000, 1000，1234} 当一个有序数组中，
         * 有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000
         *
         * 思路分析
         * 1. 在找到mid 索引值，不要马上返回
         * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
         * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
         * 4. 将Arraylist返回
         */
        public static List<Integer> binarySearchPlus(int[] arr, int leftIndex, int rightIndex, int targetValue){
            //todo 先判断是否需要查找
            //只有遍历了整个数组都没找到所要的targetValue才会到满足这个条件
            if (leftIndex>rightIndex){
                return new ArrayList<Integer>();
            }
            //todo 递归查找，中指比较,找到后不立即退出，因为二分查找前提是有序数组，需要查找其值左右是否为要找的项，左右两边查找，直到其左右两边都不等于targetValue，返回targetIndexList
            int midIndex =  (leftIndex+rightIndex)/2;
            int midValue = arr[midIndex];
            if (midValue == targetValue){
                List<Integer> targetIndexList = new ArrayList<>();
                targetIndexList.add(midIndex);
                //从midIndex左面线性查找
                int midLeftIndex = midIndex -1;
                while (true){
                    if (midLeftIndex<leftIndex || arr[midLeftIndex]!=targetValue){
                        break;
                    }
                    targetIndexList.add(midLeftIndex);
                    midLeftIndex--;
                }
                //从midIndex右面查找
                int midRightIndex = midIndex+1;
                while (true){
                    if (midRightIndex>rightIndex || arr[midRightIndex] != targetValue){
                        break;
                    }
                    targetIndexList.add(midRightIndex);
                    midRightIndex++;
                }
                return targetIndexList;
            }
            //和midValue比较，如果小于midValue，左递归，反之右递归
            if (midValue>targetValue){
                return binarySearchPlus(arr,0, midIndex-1,targetValue);
            }else {
                return binarySearchPlus(arr,midIndex+1,rightIndex,targetValue);
            }
        }
    }

## 错误code ##

package com.pl.arithmetic.search;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * <p>
     *
     * @Description: TODO
     * </p>
     * @ClassName BinarySearch
     * @Author pl
     * @Date 2020/12/20
     * @Version V1.0.0
     */
    public class BinarySearch {
    
        public static void main(String[] args) {
            int arr[] = { 1, 8, 10, 89,1000,1000, 1234 };
           // int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 , 11, 12, 13,14,15,16,17,18,19,20 };
            //
        /*  int resIndex = binarySearch(arr, 0, arr.length - 1, 11);
            System.out.println("resIndex=" + resIndex);*/
    
            List<Integer> resIndexList = binarySearchPlus(arr, 0, arr.length - 1, 1000);
            System.out.println("resIndexList=" + resIndexList);
        }
    
    
        public static int binarySearch(int[] arr,int leftIndex,int rightIndex,int targetValue){
            //todo 先判断是否需要查找
            if (leftIndex>rightIndex){
                return -1;
            }
            //todo 中指比较,递归查找
            int midIndex =  (leftIndex+rightIndex)/2;
            int midValue = arr[midIndex];
            if (midValue == targetValue){
                return midIndex;
            }
            //和midValue比较，如果小于midValue，左递归，反之右递归
            if (midValue>targetValue){
                return binarySearch(arr,0, midIndex-1,targetValue);
            }else {
                return binarySearch(arr,midIndex+1,rightIndex,targetValue);
            }
        }
    
        //完成一个课后思考题:
        /*
         * 课后思考题： {1,8, 10, 89, 1000, 1000，1234} 当一个有序数组中，
         * 有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000
         *
         * 思路分析
         * 1. 在找到mid 索引值，不要马上返回
         * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
         * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
         * 4. 将Arraylist返回
         */
        public static List<Integer> binarySearchPlus(int[] arr, int leftIndex, int rightIndex, int targetValue){
            //todo 先判断是否需要查找
            //只有遍历了整个数组都没找到所要的targetValue才会到满足这个条件
            if (leftIndex>rightIndex){
                return new ArrayList<Integer>();
            }
            //todo 递归查找，中指比较,找到后不立即退出，因为二分查找前提是有序数组，需要查找其值左右是否为要找的项，左右两边查找，直到其左右两边都不等于targetValue，返回targetIndexList
            int midIndex =  (leftIndex+rightIndex)/2;
            int midValue = arr[midIndex];
            if (midValue == targetValue){
                List<Integer> targetIndexList = new ArrayList<>();
                targetIndexList.add(midIndex);
                //从midIndex左面线性查找
                int midLeftIndex = --midIndex;
                while (true){
                    if (midLeftIndex<leftIndex || arr[midLeftIndex]!=targetValue){
                        break;
                    }
                    targetIndexList.add(midLeftIndex);
                    midLeftIndex--;
                }
                //从midIndex右面查找
                int midRightIndex = ++midIndex;
                while (true){
                    if (midRightIndex>rightIndex || arr[midRightIndex] != targetValue){
                        break;
                    }
                    targetIndexList.add(midRightIndex);
                    midRightIndex++;
                }
                return targetIndexList;
            }
            //和midValue比较，如果小于midValue，左递归，反之右递归
            if (midValue>targetValue){
                return binarySearchPlus(arr,0, midIndex-1,targetValue);
            }else {
                return binarySearchPlus(arr,midIndex+1,rightIndex,targetValue);
            }
        }
    }

输出\[5,4,5\]

### analyze ###

73,82行出错  
int midLeftIndex = --midIndex;  
int midRightIndex = ++midIndex;  
这样赋值，midIndex内存地质发生变化

[18721752-adb1807eea343693.png]: /images/20210918/1320468eb2814ce4a297f68d6cfe6879.png