Java 二分法搜索数组

概要:

二分法充分利用了元素间的次序关系,基本思想:将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如果x<a[n/2],则只要在数组a的左半部继续搜索x(这里假设数组元素呈升序排列)。如果x>a[n/2],则只要在数组a的右半部继续搜索x。

二分法的局限性:必须是在有序的元素中进行的,不能在无序的元素中使用。

| |目录

示例

package net.xsoftlab.baike;

import java.util.Arrays;

// 运用递归和二分法搜索数组元素
public class TestArraySearch {
	// 运用递归和二分查找特定整数在整型数组中的位置
	public static int binarySearch1(int[] array, int index, int beginIndex, int endIndex) {
		int midIndex = (beginIndex + endIndex) / 2;
		if (index < array[beginIndex] || index > array[endIndex] || beginIndex > endIndex) // 判断要搜索的数字是否合理
			return -1;
		if (index < array[midIndex]) { // 搜索数字位于数组前半部分
			return binarySearch1(array, index, beginIndex, midIndex - 1);// 运用递归
		} else if (index > array[midIndex]) { // 搜索数字位于数组后半部分
			return binarySearch1(array, index, midIndex + 1, endIndex);// 运用递归
		} else {
			return midIndex; // 搜索数字位于数组中间
		}
	}

	// 运用非递归和二分查找特定整数在整型数组中的位置
	public static int binarySearch2(int[] array, int index) {
		int beginIndex = 0; // 起始位置,指的是元素下标
		int endIndex = array.length - 1; // 结束位置
		int midIndex = -1;
		if (index < array[beginIndex] || index > array[endIndex] || beginIndex > endIndex) // 判断要搜索的数字是否合理
			return -1;
		// 循环判断,根据起始位置与结束位置是否相等
		while (beginIndex <= endIndex) {
			midIndex = (beginIndex + endIndex) / 2;// 获得数组中间位置
			if (index < array[midIndex]) { // 搜索数字位于数组前半部分
				endIndex = midIndex - 1; // 重新定位结束位置
			} else if (index > array[midIndex]) {// 搜索数字位于数组后半部分
				beginIndex = midIndex + 1; // 重新定位起始位置
			} else {
				return midIndex; // 搜索数字位于数组中间
			}
		}
		return -1;
	}

	public static void main(String[] args) { // java程序的主入口处
		int[] array = new int[] { 12, 3, 2, 18, 24, 15, 20 };// 声明数组并初始化
		int number = 18; // 声明变量
		int num = 1;
		Arrays.sort(array); // 二分法搜索元素之前必须对数组进行排序
		System.out.println("排序后数组:" + Arrays.toString(array));
		System.out.println("元素" + number + "所在的位置在:" + binarySearch1(array, number, 0, array.length - 1));
		System.out.println("元素" + number + "所在的位置在:" + binarySearch2(array, number));
		System.out.println("元素" + num + "所在的位置在:" + binarySearch2(array, num));
	}
}


评论关闭
评论 还能输入200
评论关闭
评论 还能输入200
  • 全部评论(0)
资料加载中...
已关注 , 取消