使用递归实现二分查找算法(查找多个值的索引)

1.设计思路

	  当找到第一个满足条件时，向左遍历，找到满足条件的就添加到集合；然后将mid添加；最后向右遍历，找到满足条件的就添加到集合；最后返回这个集合。

2.代码实现

package binarySearchManyNumber;

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

public class main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int[] Array = {3, 4, 5, 6, 7, 8, 9, 9, 9};
        System.out.println("请输入你要查询的数:");
        int num = s.nextInt();
        ArrayList<Integer> index = binarySearch(Array, 0, Array.length - 1, num);
        System.out.println(num + "的索引为:" +index);
    }

/**
 * 二分查找算法
 *
 * @param array 数组
 * @param left  左指针
 * @param right 右指针
 * @param key   要查找的值
 * @return 如果数组中存在多个目标值，则返回一个集合
 */
    public static ArrayList<Integer> binarySearch(int[] array, int left, int right, int key) {
        // 查找失败
        if (left > right) {
            return new ArrayList<Integer>();
        }
        int mid = (left + right) / 2; // 中间值的下标
        int midKey = array[mid]; // 中间值
        // 如果大于中间值，则向右递归
        if (key > midKey) {
            return binarySearch(array, mid + 1, right, key);
        } else if (key < midKey) { // 否则，向左递归
            return binarySearch(array, left, mid - 1, key);
        } else {
            // 向索引为mid的左边查找满足条件的值的索引，并添加到集合中
            ArrayList<Integer> o = new ArrayList<Integer>();
            int temp_left = mid - 1;
            while (true) {
                if (temp_left < 0 || array[temp_left] != key) {
                    break;
                }
                o.add(temp_left);
                // 向左扫描
                temp_left --;
            }
            // 将索引为mid添加到集合中
            o.add(mid);
            // 向索引为mid的右边查找满足条件的值的索引，并添加到集合中
            int temp_right = mid + 1;
            while (true) {
                if (temp_right > array.length - 1 || array[temp_right] != key) {
                    break;
                }
                o.add(temp_right);
                // 向右扫描
                temp_right++;
            }
            return o;
        }
    }
}