1 小案例

请对一个有序数组进行二分查找{1,8,10,89,1000,1234}，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数"。

2 二分查找算法的思路

在这里插入图片描述

二分查找的代码

说明：增加了找到所有的满足条件的元素下标:

课后思考题：{1,8,10,89,1000,1000，1234}当一个有序数组中，有多个相同的数值时，如何将所有的数值都查找到，比如这里的1000。

package com.sukang.search;import java.util.ArrayList;import java.util.List;/** * @description: *       二分查找算法 *       注意：使用二分查找的前提是该数组是有序的. * @author: sukang * @date: 2020-11-11 13:31 */public class BinarySearch {    public static void main(String[] args) {        int arr[] = {1,8,10,89,1000,1000,1234};        //int resIndex = binarySearch(arr,0,arr.length-1,1000);        //System.out.println("resIndex="+resIndex);        List
   
     resIndexList = binarySearch2(arr, 0, arr.length - 1, 1000);        System.out.println("resIndexList:" + resIndexList);    }    /**     * @description:     *      二分查找算法     * @param arr 数组     * @param left 左边的索引     * @param right 右边的索引     * @param findVal 要查找的值     * @return: int 如果找到就返回下标，如果没有找到，就返回-1     * @author: sukang     * @date: 2020/11/11 13:39     */        public static int binarySearch(int[] arr, int left, int right, int findVal){        // 当 left > right 时, 说明递归整个数组，但是没有找到        if(left > right){            return -1;        }        int mid = (left + right) / 2;        int midVal = arr[mid];        if(findVal > midVal){//向右递归            return binarySearch(arr, mid + 1, right, findVal);        }else if(findVal < midVal){//向左递归            return binarySearch(arr, left, mid - 1, findVal);        }else{            return mid;        }    }    //完成一个课后思考题:    /**课后思考题：{1,8,10,89,1000,1000，1234}当一个有序数组中，     *有多个相同的数值时，如何将所有的数值都查找到，比如这里的1000     *思路分析     *1.在找到mid索引值，不要马上返回     *2.向mid索引值的左边扫描，将所有满足1000，的元素的下标，加入到集合ArrayList     *3.向mid索引值的右边扫描，将所有满足1000，的元素的下标，加入到集合ArrayList     *4.将Arraylist返回     */    public static List
    
      binarySearch2(int[] arr, int left, int right, int findVal){        //当left > right时，说明递归整个数组，但是没有找到        if(left > right){            return new ArrayList
     
      ();        }        int mid = (left + right) / 2;        int midVal = arr[mid];        if(findVal > midVal){ //向右递归            return binarySearch2(arr, mid + 1, right, findVal);        }else if(findVal < midVal){//向左递归            return binarySearch2(arr, left, mid - 1, findVal);        }else{            List
      
        resIndexlist = new ArrayList
       
        ();            //向mid索引值的左边扫描，将所有满足1000，的元素的下标，加入到集合ArrayList            int temp = mid - 1;            while (true){                if(temp < 0 || arr[temp] != findVal) {//退出                    break;                }                //否则，就temp放入到resIndexlist                resIndexlist.add(temp);                temp -= 1; //temp左移            }            resIndexlist.add(mid);            //向mid索引值的右边扫描，将所有满足1000，的元素的下标，加入到集合ArrayList            temp = mid + 1;            while (true){                if(temp > arr.length - 1 || arr[temp] != findVal){//退出                    break;                }                //否则， 就temp放入到resIndexlist                resIndexlist.add(temp);                temp += 1; //temp 右移            }            return resIndexlist;        }    }}