二分法查找(Binary Search)是一種常用的查找算法,適用于有序數組或有序列表。其基本思想是將查找區間分為兩部分,將目標值與中間元素比較,如果相等則返回中間元素的位置,如果目標值小于中間元素,則在左半部分繼續查找,否則在右半部分繼續查找,直到找到目標值或查找區間為空。
以下是一個使用Java實現二分法查找的示例代碼:
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// 目標值與中間元素相等,返回中間元素的位置
if (arr[mid] == target) {
return mid;
}
// 目標值小于中間元素,在左半部分繼續查找
if (arr[mid] > target) {
right = mid - 1;
}
// 目標值大于中間元素,在右半部分繼續查找
else {
left = mid + 1;
}
}
// 查找區間為空,未找到目標值
return -1;
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11};
int target = 7;
int result = binarySearch(arr, target);
if (result != -1) {
System.out.println("目標值在數組中的位置為:" + result);
} else {
System.out.println("目標值在數組中未找到");
}
}
}
在上述示例代碼中,binarySearch
方法接收一個有序數組和目標值作為參數,使用兩個指針left
和right
來表示查找區間的左右邊界。在每次迭代中,計算中間位置mid
并與目標值進行比較,根據比較結果調整左右邊界,最終找到目標值的位置或確定目標值不存在。在main
方法中,我們定義了一個有序數組arr
和目標值target
,并調用binarySearch
方法進行查找,輸出結果為目標值在數組中的位置或未找到的提示信息。