- 基本介绍
- 二分查找要求是查询一个有序数组
- 分递归和非递归查找
- 查找思路
- 代码演示——
package DataStructures.Search; import java.util.ArrayList; import java.util.List; public class BinarySearch { public static void main(String[] args) { //二分查找,数组必须是有序的(实例默认从小到大) int arr[] = {1, 8, 10, 89, 1000,1000,1000,1000, 1234}; //int resIndex = binarySearch(arr, 0, arr.length - 1, 11); //System.out.println(resIndex); //优化后 ListresIndexList = binarySearch2(arr,0,arr.length-1,1000); System.out.println("resIndexList="+ resIndexList); } 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]; if (findVal > midVal) { //向右递归 return binarySearch(arr, mid + 1, right, findVal); } else if (findVal < midVal) { //想左递归 return binarySearch(arr, left, mid - 1, findVal); } else { return mid; } } public static List binarySearch2(int arr[], int left, int right, int findVal) { if (left > right) { return new ArrayList (); } int mid = (left + right) / 2; int midVal = arr[mid]; if (findVal > midVal) { //向右递归 return binarySearch2(arr, mid + 1, right, findVal); } else if (findVal < midVal) { //想左递归 return binarySearch2(arr, left, mid - 1, findVal); } else { List resIndexList = new ArrayList (); int temp = mid - 1; while (true) { if (temp < 0 || arr[temp] != findVal) { break; } resIndexList.add(temp); temp -= 1; } resIndexList.add(mid); temp = mid + 1; while (true) { if (temp > arr.length - 1 || arr[temp] != findVal) { break; } resIndexList.add(temp); temp+=1; } return resIndexList; } } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)