1. 二分查找
请对一个有序数组进行二分查找 {1,8, 10, 89, 1000, 1234}
,输入一个数看看该数组是否存在此数,并且求出下标,如果没有就提示”没有这个数”
1.1 实现思路
1.2 代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
| public class BinarySearch {
public static void main(String[] args) {
int[] arr = {1,1,2,3,4,5,6,7,8,9}; List<Integer> list = binarySearch(arr, 0, arr.length-1,1); System.out.println(list.toString()); }
public static List<Integer> binarySearch(int[] arr,int left,int right,int searchVal){ if(left>right) { return new ArrayList<Integer>(); } int mid = (left+right)/2; if(searchVal<arr[mid]) { return binarySearch(arr, left, mid-1, searchVal); }else if(searchVal > arr[mid]) { return binarySearch(arr, mid+1, right, searchVal); }else { List<Integer> list = new ArrayList<Integer>(); int temp = mid - 1 ; while(true) { if(temp<0 || arr[temp] != searchVal) { break; } list.add(temp); temp -=1; } list.add(arr[mid]); temp = mid + 1 ; while(true) { if(temp>right || arr[temp] != searchVal) { break; } list.add(temp); temp +=1; } return list; } } }
|