折半查找(二分查找)是一种常见且高效的查找算法,适用于有序数组。其基本思想是首先将数组按照中间位置折半,然后判断待查找元素与中间元素的大小关系,从而确定待查找元素在左半部分还是右半部分。通过不断折半和判断,最终找到待查找元素或确定其不存在。
以下是一个使用折半查找的示例代码:
public class BinarySearch {
public static int binarySearch(int[] array, int target) {
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] == target) {
return mid;
} else if (array[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 表示未找到
}
public static void main(String[] args) {
int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int target = 6;
int result = binarySearch(array, target);
if (result != -1) {
System.out.println("元素 " + target + " 的索引位置为 " + result);
} else {
System.out.println("元素 " + target + " 不存在于数组中");
}
}
}
以上代码中,binarySearch
方法接收一个有序数组 array
和待查找元素 target
,并返回待查找元素在数组中的索引位置,如果不存在则返回 -1。算法使用了两个指针 left
和 right
来表示当前查找的区间范围,通过循环不断缩小区间,直到找到待查找元素或确定不存在为止。
需要注意的是,前提是数组必须是有序的。如果数组无序,可以在查找之前先对数组进行排序。