java實作二分法查找

什麼是二分法查找：

二分法也就是折半查找，在有序的數列中尋找指定的元素，設定最小索引（low）和最大索引（height-1）還有中間值mid（(low height-1)/2），這種查找，如果中間值比指定元素小讓low=mid 1,如果中間值比指定元素大，讓height =mid-1；

程式碼實作：（免費影片教學分享：java影片教學）

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
 
public class Main2 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
				int arr[] = { 2, 5, 6, 8, 9, 4, 7 };
				Arrays.sort(arr);
				int deix（索引） = getxiabiao(arr, 7);
				
			}
			public static int getxiabiao(int[] arr, int key) {
				int heigh = arr.length-1;
				int low = 0;
				int mid = 0;
				while (low <= heigh) {
					mid = low + (heigh - low)/2;
					if (arr[mid] == key) {
						return mid;
					} else if (arr[mid] < key) {
						low = mid + 1;
					} else if (arr[mid] > key) {
						heigh = mid - 1;
					}
				}
				return -1;
			}
		}

中間值的設定有兩種方法；

演算法一： mid = (low high) / 2

演算法二： mid = low (high – low)/2

乍看起來，演算法一簡潔，演算法二提取之後，跟算法一沒有什麼差別。但是實際上，差別是存在的。

演算法一的做法，在極端情況下，(low high)存在著溢出的風險，進而得到錯誤的mid結果，導致程式錯誤，而演算法二能夠保證計算出來的mid，一定大於low ，小於high，不存在溢出的問題。

相關文章教學推薦：java入門教學

#

以上是java實作二分法查找的詳細內容。更多資訊請關注PHP中文網其他相關文章！