查找算法java实现

2023-12-20 03:40| 来源: 网络整理| 查看: 265

二分查找一、基本思路二、算法分析三、代码实现

一、基本思路

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

基本思路：首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

简单来说：就是递归的把序列分成前后两部分进行查找。

举例：有一序列1, 8, 10, 89, 1000,1234要求查找序列中是否含有89

计算有序序列的mid=10，由于89>10，所以在序列89，1000，1234中查找计算有序序列的mid=1000，由于89 int[] arr = {1, 8, 10, 89, 1000,1000,1000,1234}; System.out.println("序列中是否含有元素：" + binarySearch(arr, 0, arr.length - 1, 1000)); System.out.println("序列中指定元素的下标：" + binarySearch2(arr, 0, arr.length-1, 1000)); } /** * * @param arr 数组 * @param left 左边索引 * @param right 右边索引 * @param value 要查找的值 * @return 如果找到就返回true，如果没有找到，就返回false */ public static boolean binarySearch(int[] arr, int left, int right, int value) { if (left > right) { return false; } int mid = (left + right) / 2; int midVal = arr[mid]; if (value > midVal) {//向右递归 return binarySearch(arr, mid + 1, right, value); } else if (value return true; } } /** * * @param arr 数组 * @param left 左边索引 * @param right 右边索引 * @param value 要查找的值 * @return 返回满足条件的元素的所有下标 */ public static List binarySearch2(int[] arr, int left, int right, int value) { if (left > right) { return new ArrayList(); } int mid = (left + right) / 2; int midVal = arr[mid]; if (value > midVal) {//向右递归 return binarySearch2(arr, mid + 1, right, value); } else if (value List list = new ArrayList(); int temp = mid - 1;//向左边查找 while (true) { if (temp if (temp > arr.length - 1 || arr[temp] != value) { break; } list.add(temp); temp += 1; } return list; } } }

测试序列： int arr[] = {1, 8, 10, 89, 1000,1000,1000,1234};查找是否含有元素1000 测试结果：

非递归实现： /** * @author dankejun * @create 2020/9/189:30 */ public class BinarySearchNoRecur { public static void main(String[] args) { int[] arr = {1, 3, 8, 10, 11, 67, 100}; int index = binarySearch(arr, 8); System.out.println("index=" + index); } /** * 二分查找的非递归实现 * @param arr 待查找的数组,升序排列 * @param target 待查找的目标数 * @return 返回目标数的下标，-1表示未找到 */ public static int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length - 1; while (left return mid; } else if (arr[mid] > target) { right = mid - 1;//需要向左边查找 } else { left = mid + 1;//需要向右边查找 } } return -1; } }

测试序列：int[] arr = {1, 3, 8, 10, 11, 67, 100}，查找是否含有元素8 测试结果：在这里插入图片描述

【本文地址】

查找算法java实现

查找算法java实现

今日新闻

推荐新闻