二分查找算法的思路及代码实现

package Search;

import java.util.ArrayList;
import java.util.List;

/*
1.二分查找：
1.1首先确定该数组的中间下标-->mid = (left + right) / 2;初始化left = 0,right = arr.length - 1
1.2 然后让需要查找的数findValue 和 arr[mid] 比较
1.3 如果 findValue > arr[mid],说明要找的数在mid 的右边,因此需要递归向右查找
1.4 如果 findValue < arr[mid]，说明要找的数在mid 的左边,因此需要递归向左查找
1.5 如果findValue == arr[mid],说明找到，就返回

递归退出的条件：
1）找到就结束递归findValue == arr[mid]
2）递归完整个数组，仍然没有找到findValue,也需要结束递归，条件是当left > right 的时候

 */
public class BinarySearch {
    public static void main(String[] args) {
        int [] arr = {1,2,4,8,8,8,23,30};
        List<Integer> list = binarySearch02(arr,8,0, arr.length - 1);
        if(list.size() != 0){
            System.out.println(list);
        } else{
            System.out.println("没有找到--");
        }
    }
    //要查找的数组必须是 有序 的
    public static int binarySearch(int [] arr, int findVal,int left, int right){
        //当left > right 时，说明没有找到
        if(left > right){
            return -1;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];

        if(findVal > midVal){
            //向右递归
            return binarySearch(arr,findVal,mid + 1, right);
        } else if (findVal < midVal){
            return binarySearch(arr,findVal,left,mid - 1);
        }else{
            return mid;
        }
    }

    //如果要找到 数组中等于findVal的 所有值
    //思路：找到mid值时，不要马上返回
    //向mid索引值的左边扫描，将所有==findVal的所有值的下标加入ArrayList中
    //向mid索引值的右边扫描，将所有==findVal的所有值的下标加入ArrayList中
    //要查找的数组必须是 有序 的
    public static List<Integer> binarySearch02(int [] arr, int findVal,int left, int right){
        //当left > right 时，说明没有找到，返回一个空的集合
        if(left > right){
            return new ArrayList<Integer>();
        }

        int mid = (left + right) / 2;
        int midVal = arr[mid];

        if(findVal > midVal){
            //向右递归
            return binarySearch02(arr,findVal,mid + 1, right);
        } else if (findVal < midVal){
            return binarySearch02(arr,findVal,left,mid - 1);
        }else{
            List<Integer> list = new ArrayList<>();
            int temp = mid - 1;
            while (true){
                if(temp < 0 || arr[temp] != findVal){
                    break;
                }

                list.add(temp);
                temp -= 1;
            }
            list.add(mid);

            temp = mid + 1;
            while (true){
                if (temp > arr.length - 1 || arr[temp] != findVal){
                    break;
                }
                list.add(temp);
                temp += 1;
            }

            return list;
        }
    }

}