二分查找算法
1. 二分查找算法介绍
- 二分查找法只适用于从有序的数列中进行查找(比如数字和字母等),将数列排序后再进行查找。
- 二分查找法的运行时间为对数时间 O(㏒₂n) ,即查找到需要的目标位置最多只需要㏒₂n 步,假设从[0,99]的队列(100 个数,即 n=100)中寻到目标数 30,则需要查找步数为㏒₂100 , 即最多需要查找 7 次( 2^6 < 100 < 2^7)
2. 二分查找算法(非递归)代码实现
数组 {1,3, 8, 10, 11, 67, 100}, 编程实现二分查找, 要求使用非递归的方式完成.
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
| public class BinarySearchNoRecur {
public static void main(String[] args) { int[] arr = {1,2,3,5,7,8,9,76}; int binarySearch = binarySearch(arr,8); System.out.println(binarySearch);
}
public static int binarySearch(int[] arr,int target) { int left = 0; int right = arr.length-1; while(left <= right) { int mid = (left + right)/2; if(arr[mid] == target) { return mid; }else if(arr[mid] < target) { left = mid + 1; }else if(arr[mid] > target) { right = mid - 1; } } return -1; }
}
|
- 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗:40.6 MB, 在所有 Java 提交中击败了75.78%的用户
3. 二分查找算法(递归)代码实现
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
| 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; } } }
|
☆