查找算法之一：二分查找（递归实现） |
您所在的位置：网站首页 › 二分查找递归算法c语言 › 查找算法之一：二分查找（递归实现） |
|
二分查找的递归实现
思路分析代码实现
思路分析
1、确定该序列的中间的下标mid： mid = （left + right）/2； 2、让需要查找的数findVal 与 arr[mid]进行比较： （1）findVal > midVal，则进行向右递归，查找findVal； 递归的边界条件是：mid+1，right （2）findVal < midVal，则进行向左递归，查找findVal； 递归的边界条件是：left，mid-1 （3）findVal == midVal，则表明找到了待查找的findVal， 直接return mid的坐标值； 3、什么时候结束递归？ （1）找到就结束递归，直接return mid； （2）递归查找完整个数组，仍然没有找到findVal，也需要结束递归， 此时，left > right。 4、对于二分查找的功能的完善， 即：当待查找的findVal在序列中出现多次时，可以返回所有的出现位置的索引值 == >通过集合来实现该功能： （1）当找到findVal时，即midVal == findVal时， 定义一个ArrayList int temp =mid;//暂存mid，用于向mid的前后遍历 然后从mid到的索引，先开始向前遍历： while(–temp>=0 && arr[temp] == findVal) 接着从mid到的索引，先开始向后遍历： while(++temp 即：保证数下标不越界的同时，又找到了== findVal的元素 直到两个while循环结束，return 这个ArrayList即可； （2）如果出现left > right，表明找不到==findVal的值，直接return一个空的ArrayList即可 代码实现1、基础的二分查找 【对于findVal只要查找到序列中一个与它相等，就立即返回对应的下标值】 public static int binarySearch(int[] arr,int left,int right,int findVal) { //递归的终止条件之二：找不到该元素 if(left > right) { return -1; } //没有查找完该序列的时候 int mid = (left + right)/2; int midVal = arr[mid]; // System.out.println("二分查找"); //判断midVal与findVal的大小关系 if(findVal > midVal) {//（1）findVal > midVal，则进行向右递归，查找findVal； return binarySearch(arr, mid+1, right, findVal); }else if(findVal 递归的终止条件之二 if(left > right) { return new ArrayList(); } //还没有递归结束的时候 int mid = (left+right)/2; int midVal = arr[mid]; if(findVal > midVal) {//需要向右递归 return binarySearch(arr, mid+1, right, findVal); }else if(findVal =0 && arr[temp]==findVal) { list.add(temp); } //将mid加入list中 list.add(mid); //向右查找有没有==findVal的元素 while(++mid |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |