[JAVA]二分搜尋(Binary seach)重複目標值

2022-06-05 置頂文章

113
0
algorithm

  // 進行BinarySeach前提，先準備好有序陣列
  // 若目標值小於中間值，則向左遞歸查找
  // 若目標值大於中間值，則向右遞歸查找
  // 若目標值等於中間值，則直接回傳中間值索引
  // 若查找不到目標值，例如left > right，即退出遞歸

// 二分搜尋
public class BinarySearch {
  // 進行BinarySeach前提，先準備好有序陣列
  // 若目標值小於中間值，則向左遞歸查找
  // 若目標值大於中間值，則向右遞歸查找
  // 若目標值等於中間值，則直接回傳中間值索引
  // 若查找不到目標值，例如left > right，即退出遞歸
  public static void main(String[] args) {
    int[] array = {1,4,23,23,23,56,356,754,975};
    List<Integer> indexList = doBinarySearching(array, 0, array.length-1, 23);
    if (indexList.size() == 0) {
      System.out.println("沒有查找到目標值！");
    } else {
      System.out.println("目標值索引為 : " + indexList);
    }
  }

  /**
   * 在陣列中找到目標值即回傳索引
   * @param array
   * @param left
   * @param right
   * @param value
   * @return
   */
  public static List<Integer> doBinarySearching(int[] array, int left, int right, int value) {
    List<Integer> indexList = new ArrayList<>();
    if (left > right) {
      return new ArrayList<>();
    }

    int middle = (left + right) / 2;
    int midValue = array[middle];
    if (value < midValue) {
      // 向左
      return doBinarySearching(array, left, middle-1, value);
    } else if (value > midValue) {
      // 向右
      return doBinarySearching(array, middle+1, right, value);
    } else {
      // 找到目標值不馬上回傳，繼續從目標值左邊查找
      int temp = middle - 1;
      while (true) {
        if (temp < 0) {
          break;
        }
        if (array[temp] == value) {
          indexList.add(temp);
        }
        // 繼續往左
        temp -= 1;
      }
      indexList.add(middle);
      // 找到目標值不馬上回傳，繼續從目標值右邊查找
      temp = middle + 1;
      while (true) {
        if (temp > array.length-1) {
          break;
        }
        if (array[temp] == value) {
          indexList.add(temp);
        }
        // 繼續往右
        temp += 1;
      }
    }
    return indexList;
  }


}

如有敘述錯誤，還請不吝嗇留言指教，thanks!

binarySearch

回首頁