[[395207]]

需求

對于一個有序的數(shù)組進行二分查找{1,8,10,89,1000,1234}，輸入一個數(shù)看看該數(shù)組是否存在此數(shù)，并求出下標，如果沒有就提示”沒有這個數(shù)據(jù)”。

思路分析

1. 首先確定該數(shù)組中間的下標 mid=(left+right)/2.
2. 然后讓需要查找的數(shù)findValue和arr[mid]比較，findValue > arr[mid]，說明要查找的數(shù)在arr[mid]的右邊，因此向右遞歸.findValue < arr[mid]，說明要查找的數(shù)在arr[mid]的左邊，因此向左遞歸.findValue == arr[mid]，說明找打，就返回。
3. 退出遞歸的條件找到就結(jié)束遞歸。遞歸完整個數(shù)組仍然沒有找到findValue，需要結(jié)束遞歸，即當 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("查找次數(shù)：" + count); 
        /* 
        indexList = [1, 0] 
        查找次數(shù)：6 
         */ 
    } 
 
    /** 
     * 二分查找,查找符合值得所有索引集合 
     * 
     * @param arr       數(shù)組 
     * @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; 
        } 
    } 
} 

 【編輯推薦】