查詢演算法
順序查詢
程式碼很簡單,迴圈比較即可。
public static int search(int[] array, int num) { int position = -1; for (int i = 0; i < array.length; i++) { if (array[i] == num) { return i; } } return position; }
折半查詢
前提:必須是有序的資料。
基本思想:把一個有序的資料一份為二。然後判斷是比目標資料大了還是小了,如果小了往左邊的部分找;如果大了往右邊的資料找。確定了找的方向後再次把資料一分為二,繼續上面的步驟直到找到為止。這裡的重複執行就用遞迴思想。
public static void binerySearch(int[] array, int start, int end, int num) { int position = -1; int middle = (start + end) / 2; if (array[middle] == num) { System.out.print("找到第" + middle + "個位置"); } else if (array[middle] > num) { binerySearch(array, start, middle - 1, num); } else if (array[middle] < num) { binerySearch(array, middle + 1, end, num); } }
方法測試:
public static void main(String[] args) { int[] array = new int[]{7, -3, 0, 20, 8, 9}; int position = search(array, 20); if (position == -1) { System.out.println("沒有找到該數"); } else { System.out.println("找到第" + position + "個位置"); } int[] array2 = new int[]{-2,5,10,16,87,99}; binerySearch(array2,0,array2.length,10); }