赞
踩
目录
二分查找法(Binary Search)算法,也叫折半查找算法。二分查找针对的是一个有序的数据集合,查找思想有点类似于分治思想。每次都通过跟区间的中间元素对比,将带查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为0。
例:请对一个有序数组进行二分查找{1,8, 10, 89, 1000, 234}输入一个数看看该数组是否存在此数,并且求出下标,如果没有就提示"没有这个数"。
定义变量:
mid:要进行二分查找的数组的中间下标;
left:要进行二分查找的数组的最左边的下标
right:要进行二分查找的数组的最右边的下标
findVal:我们要进行二分查找的数字
1,首先确定该数组的中间的下标mid= (left+right)/2
2,然后让需要查找的数findVal和arr[mid]比较:
2.1 findVal>arr[mid],说明要查找的数在mid的右边,因此需要递归的向右查找
2.2 findVal <arr[mid],说明你要查找的数在mid的左边,因此需要递归的向左查找。
2.3 findval==arr[mid]说明找到,就返回 。
3,结束递归的条件:
1)找到就结束递归。
2)递归完整个数组,仍然没有找到findval,就需要结束递归。
3)当left> right就需要退出递归。
4,弊端:
当一个有序数组中,有多个相同的数值时,只会返回一个值的位置的索引。
- //注意二分查找的前提是:该数组是有序的
- public class BinarySearch {//二分查找
-
- public static void main(String[] args) {
- //测试二分查找:
- int[] arr = {1,8,10,89,1000,1234};
- int val = binarySearch2(arr, 0, arr.length - 1, 36);
- System.out.println(val);
- }
-
- /*二分查找【不能查找重复的值的索引,相同的值只会返回一个值的索引】
- arr 数组
- left 数组最左边的索引
- right 数组最右边的索引
- findVal 要查找的值
- 如果找到就返回下标,如果没有找到就返回-1
- * */
- public static int binarySearch(int[] arr, int left, int right, int findVal) {
- // findVal < arr[0] || findVal > arr[arr.length - 1]说明要查找的findVal值再数组中不存在
- //当left>right时说明,已经递归了整个数组,但是没有findVal值
- if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {//当满足其中任意一个条件时,就要退出递归。
- return -1;
- }
- int mid = (left + right) / 2;//mid表示数组中间的下标
- int midVal = arr[mid];//midVal表示数组中间的值
- if (findVal > midVal) {
- //向右递归
- return binarySearch(arr, mid + 1, right, findVal);
- } else if (findVal < midVal) {
- //向左递归
- return binarySearch(arr, left, mid - 1, findVal);
- } else {//表示:findVal==midVal找到要查找的值
- return mid;
- }
- }
- }
- //注意二分查找的前提是:该数组是有序的
- public class BinarySearch {//二分查找
-
- public static void main(String[] args) {
- //测试:当有数组里多个相同的数值时,将所有的数值都查找到返回下标索引。比如这里的1000
- int[] arr = {1,8, 10, 89, 1000, 1000, 1 ,34};
- List val = binarySearch2(arr, 0, arr.length - 1, 1000);
- System.out.println(val);
- }
-
-
- /*二分查找优化【查找出多个相同的的值的下标索引】
- arr 数组
- left 数组最左边的索引
- right 数组最右边的索引
- findVal 要查找的值
- 如果找到就返回下标,如果没有找到就返回-1
- * */
- public static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
- if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
- return new ArrayList<Integer>();
- }
- int mid = (left + right) / 2;//mid表示数组中间的下标
- int midVal = arr[mid];//midVal表示数组中间的值
- if (findVal > midVal) {
- //向右递归
- return binarySearch2(arr, mid + 1, right, findVal);
- } else if (findVal < midVal) {
- //向左递归
- return binarySearch2(arr, left, mid - 1, findVal);
- } else {//表示:findVal==midVal【经过前面的递归,最终都会有findVal==midVal】
- /*
- * 思路分析:
- * 1,在找到mid索引值,不马上返回
- * 2,向mid索引值的左边扫描,将所有满足findVal的值的下标加入到ArrayList集合里
- * 3,向mid索引值的右边扫描,将所有满足findVal的值的下标加入到ArrayList集合里
- * 4,将ArrayList集合返回
- * */
- ArrayList<Integer> integers = new ArrayList<>();
- //向mid索引值的左边扫描,将所有满足findVal的值的下标加入到ArrayList集合里
- int temp = mid - 1;//temp表示向左扫描的索引
- while (true) {
- if (temp < 0 || arr[temp] != findVal) {//退出
- break;
- }
- //否则,就把temp放入集合integers中
- integers.add(temp);
- temp -= 1;
- }
- integers.add(mid);//刚好mid就是要找的findVal值
- //向mid索引值的右边扫描,将所有满足findVal的值的下标加入到ArrayList集合里
- temp = mid + 1;//temp表示向右扫描的索引
- while (true) {
- if (temp > arr.length - 1 || arr[temp] != findVal) {//退出
- break;
- }
- //否则,就把temp放入集合integers中
- integers.add(temp);
- temp += 1;
- }
- return integers;
- }
- }
非递归法相对于递归法就要简单的多,只是while循环和if-else的嵌套使用就可以实现。
- public class BinaryDearchNoRecur {//二分查找的非递归实现
-
- public static void main(String[] args) {
- //测试
- int[] arr = {1, 3, 8, 10, 11, 67, 100};
- int index = binaryDearch(arr, 13);
- System.out.println("index=" + index);
- }
-
- /**
- * 二分查找的非递归实现
- * @param arr 待查找的数组,arr是升序排列
- * @param target 需要查找的数
- * @return 返回对应数组下标,没有返回-1
- */
- public static int binaryDearch(int[] arr, int target) {
- int left = 0;//left表示数组最左边的索引
- int right = arr.length - 1;//表示数组最右边的索引
- while (left <= right) {//说明可以继续查找
- int mid = (left + right) / 2;//mid表示数组中间的索引
- if (arr[mid] == target) {
- return mid;
- } else if (arr[mid] > target) {
- right = mid - 1;//需要向左边查找
- } else {
- left = mid + 1;//需要向右边查找
- }
- }
- return -1;
- }
- }
长风破浪会有时,直挂云帆济沧海!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。