需求

對於一個有序的陣列進行二分查詢{1,8,10,89,1000,1234}，輸入一個數看看該陣列是否存在此數，並求出下標，如果沒有就提示”沒有這個資料”。

思路分析首先確定該陣列中間的下標 mid=(left+right)/2.然後讓需要查詢的數findValue和arr[mid]比較，findValue > arr[mid]，說明要查詢的數在arr[mid]的右邊，因此向右遞迴.findValue < arr[mid]，說明要查詢的數在arr[mid]的左邊，因此向左遞迴.findValue == arr[mid]，說明找打，就返回。退出遞迴的條件找到就結束遞迴。遞迴完整個陣列仍然沒有找到findValue，需要結束遞迴，即當 left > right程式碼案例

package com.xie.search;import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class BinarySearch {    static int count = 0;    public static void main(String[] args) {        int[] arr = new int[102];        arr[0] = 1;        arr[1] = 1;        for (int i = 2; i < 102; i++) {            arr[i] = i;        }        List<Integer> indexList = binarySearch(arr, 0, arr.length - 1, 1);        System.out.println("indexList = " + indexList);        System.out.println("查詢次數：" + count);        /*        indexList = [1, 0]        查詢次數：6         */    }    /**     * 二分查詢,查詢符合值得所有索引集合     *     * @param arr       陣列     * @param left      左邊索引     * @param right     右邊索引     * @param findValue 查詢的值     * @return 找到就返回所有索引的集合，沒有就返回空     */    public static List<Integer> binarySearch(int[] arr, int left, int right, int findValue) {        count++;        List<Integer> indexList = new ArrayList<Integer>();        //當left > right時，說明遞迴完畢        if (left > right) {            return new ArrayList<Integer>();        }        int mid = (left + right) / 2;        int midVal = arr[mid];        if (findValue > midVal) {            //查詢的值比中間值大，向右遞迴            return binarySearch(arr, mid + 1, right, findValue);        } else if (findValue < midVal) {            //查詢的值比中間值小，向左遞迴            return binarySearch(arr, left, mid - 1, findValue);        } else {            //如果找到了，再向左掃描，將滿足條件的加入indexList            int temp = mid - 1;            while (true) {                if (temp < 0 || arr[temp] != findValue) {                    break;                }                indexList.add(temp);                temp--;            }            //再向右掃描,將滿足條件的加入indexList            temp = mid + 1;            while (true) {                if (temp > right || arr[temp] != findValue) {                    break;                }                indexList.add(temp);                temp++;            }            indexList.add(mid);            return indexList;        }    }}