第八章：查找算法

二分查找算法的介绍：
二分查找算法是对有序数组进行查找的算法。通过将需要查找的值与数组中间位置的值比较，从而确定要查找的数在中间值的左半部分或者右半部分，利用递归的思想，得到最终的结果

package com.atguigu07.search;

import java.util.ArrayList;
import java.util.Scanner;


public class BinarySearch {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] array = {1, 1, 1, 4, 5, 6, 78, 78, 98, 99, 99};//二分查找使用的数组必须是有序的
        System.out.println("请输入要使用哪种版本的二分查找算法：1（基础版）/2（升级版）");
        int order = scanner.nextInt();
        if (order == 1) {
            boolean loop = true;
            while (loop) {
                System.out.println("请输入想要查找的元素：");
                int value = scanner.nextInt();
                int result = binarySearch(array, 0, array.length - 1, value);
                if (result != -1) {
                    System.out.println("找到了该元素，索引是" + result);
                } else {
                    System.out.println("找不到该元素！");
                }
            }
        } else if (order == 2) {
            boolean loop = true;
            while (loop) {
                System.out.println("请输入想要查找的元素：");
                int value = scanner.nextInt();
                ArrayList integerArrayList = binarySearchUpdate(array, 0, array.length - 1, value);
                if (integerArrayList.size() == 0) {
                    System.out.println("找不到该元素哦！");
                } else {
                    System.out.println("找到了该元素，索引是" + integerArrayList);
                }
            }
        } else {
            System.out.println("你输入的是啥指令，好好看一下提示！");
        }
    }

    
    public static int binarySearch(int[] array, int left, int right, int value) {
        //如果左边界大于右边界，说明没有找到需要找的那一个元素，递归应该结束
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;//中间界点
        if (value == array[mid]) {
            //如果中间值就是我们要找的元素，那么直接返回元素的索引
            return mid;
        } else if (value < array[mid]) {
            //如果目标元素在中间元素的左边，那么就开启左递归
            return binarySearch(array, left, mid - 1, value);
        } else if (value > array[mid]) {
            //如果目标元素在中间值的右边，那么就开启右递归
            return binarySearch(array, mid + 1, right, value);
        } else {
            return -1;
        }
    }

    
    public static ArrayList binarySearchUpdate(int[] array, int left, int right, int value) {
        int mid = (left + right) / 2;//中间节点的索引
        int midValue = array[mid];//中间元素的值
        if (left > right) {
            //如果左边界小于右边界的话，那么就直接返回空的ArrayList，因为找不到
            return new ArrayList();
        }
        if (value < midValue) {
            //如果要查找的元素在中间元素的左边
            return binarySearchUpdate(array, left, mid - 1, value);
        } else if (value > midValue) {
            //如果要查找的元素在中间元素的右边
            return binarySearchUpdate(array, mid + 1, right, value);
        } else {
            //此时说明已经找到了要查找元素的索引，继续查找它的左边和右边，将和它相同的值的元素全部找出来
            ArrayList arrayList = new ArrayList<>();//存在找到的元素的索引
            //在左边继续寻找，看有没有和目标元素相同的元素
            int temp = mid - 1;
            while (true) {
                if (temp < 0 || array[temp] != value) {
                    //temp < 0:表示如果索引小于0了，说明找完全部了都没有找到
                    //array[temp] != value:如果不满足这个条件也会跳出循环，因为二分查找是一个有序数组，和目标元素相同的元素一定就在它
                    //的左边或者右边，一旦发现没有和目标元素相等的元素，就说明没有和它相等的元素
                    break;
                }
                arrayList.add(temp);
                temp--;
            }
            arrayList.add(mid);//先把左边的找到，再把中间找到的那一个放进去
            //向右边寻找，和左边的差不多
            temp = mid + 1;
            while (true) {
                if (temp > array.length - 1 || array[temp] != value) {
                    //这里跳出循环的理由和上面的一样
                    break;
                }
                arrayList.add(temp);
                temp++;
            }
            return arrayList;
        }
    }
}