转载请注明出处:
快速定位 一个有序数列中 某一个元素的位置;
共有三种思路:
第一种:使用 for 循环,匹配元素值 与循环变量的值是否相等,相等则循环变量时的 i 则为元素位置
第二种:使用 二分法 与递归,二分法为折半思想,通过递归折半,找到元素的位置
第三种:使用 二分发 与 while 循环,在while 循环中,以 元素值得 最大值与最小值关系,在while 循环中,通过二分法,不断修改 元素区间的最大值与最小值
实现:
第一种 for 循环的代码省略。
第二种,使用 二分法 与 递归 与 第三种实现方式如下:
转载请注明出处: 快速定位 一个有序数列中 某一个元素的位置; 共有三种思路: 第一种:使用 for 循环,匹配元素值 与循环变量的值是否相等,相等则循环变量时的 i 则为元素位置 第二种:使用 二分法 与递归,二分法为折半思想,通过递归折半,找到元素的位置 第三种:使用 二分发 与 while 循环,在while 循环中,以 元素值得 最大值与最小值关系,在while 循环中,通过二分法,不断修改 元素区间的最大值与最小值 实现: 第一种 for 循环的代码省略。 第二种,使用 二分法 与 递归 与 第三种实现方式如下: 复制代码 package com.example.demo.lettcode; /** * 使用二分查找,快速定位元素位置和是否存在 * 当使用二分查找时,必须保证是有序数列,只有有序数列才能进行大小的左右分边 */ public class BinarySearch { public static void main(String[] args) { int arr[] = {1,3,4,5,6,7,8,12}; System.out.println(arr.length); // 使用递归与二分法 int index = binarySearch(arr,4,0,arr.length-1); System.out.println(index); // 使用while 循环与二分法 int index2 = cycleFind(arr,4); System.out.println(index2); } /** * 使用递归与二分法 * @param arr * @param value * @param start * @param end * @return */ public static int binarySearch(int[] arr, int value, int start, int end) { //判断在有序列表中是否存在 if (value < arr[start] || value > arr[end] || start > end) { return -1; } int middle = (start + end) / 2; int index = 0; if (arr[middle] > value) { //位于中间值得左边 index = binarySearch(arr, value, start, middle - 1); } else if (arr[middle] < value) { // 位于中间值得右边 index = binarySearch(arr, value,middle + 1, end ); } else { return middle; } return index; } /** * 使用while循环与二分法 * @param arr * @param value * @return */ public static int cycleFind(int[] arr, int value) { int low = 0; int middle = 0; int high = arr.length - 1; while (low <= high) { middle = (low + high) / 2; if (arr[middle] > value) { high = middle - 1; } else if (arr[middle] < value) { low = middle + 1; } else { return middle; } } return -1; } } 复制代码 分析: 使用递归方式时,递归的次数和深度都是log2 N,每次所需要的辅助空间都是常数级别的: 空间复杂度:O(log2N ) 非递归方式时,空间复杂度为 O(1) 标签: 算法与数据结构
分析:
使用递归方式时,递归的次数和深度都是log2 N,每次所需要的辅助空间都是常数级别的: 空间复杂度:O(log2N )
非递归方式时,空间复杂度为 O(1)
标签: 算法与数据结构