二分查找只适用于从有序的数列中进行查找,将数列排序后再进行查找
二分查找算法的运行时间为 O(log2 n),即 100 个数,最多需要 7 次:(2 ^ 6 < 100 < 2 ^ 7)
当找到或者递归完整个数组后结束递归!
package cn.imut;
import sun.security.provider.MD2;
public class BinarySearch {
public static void main(String[] args) {
int[] arr = {1, 3, 4, 7, 9, 11, 14, 15, 20, 1000};
int resIndex = binarySearch(arr,0,arr.length - 1, 1000);
System.out.println("要查询的数字的下标为:" + resIndex);
}
/**
* 二分查找
* @param arr 数组
* @param left 左索引
* @param right 右索引
* @param findVal 要查找的数字
* @return 返回其下标,没找到则返回 -1
*/
public static int binarySearch(int[] arr, int left, int right, int findVal) {
//当left > right 时,说明数组已经递归完毕,但是还没有找到!
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;
}
}
}
倘若有多个相同的数字要查询,eg:{1, 8, 10, 22, 1000, 1000, 1000, 22222},查询数字 1000
public static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
//当left > right 时,说明数组已经递归完毕,但是还没有找到!
if(left > right) {
return new ArrayList<Integer>();
}
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 {
//此时不能直接返回,而是向两侧分别查询
ArrayList<Integer> list = new ArrayList<>();
int temp = mid - 1;
while (temp >= 0 && arr[temp] == findVal) {
//找到,放入集合
list.add(temp);
temp -= 1;
}
temp = mid + 1;
while (temp <= arr.length - 1 && arr[temp] == findVal) {
list.add(temp);
temp += 1;
}
return list;
}
}
package cn.imut;
public class BinarySearchNoRecur {
public static void main(String[] args) {
int[] arr = {1, 3, 6, 19, 22, 40};
int index = binarySearch(arr,40);
System.out.println(index);
}
/**
* 二分查找非递归实现
* @param arr 数组,升序排序
* @param target 要查找的数
* @return 返回对应下标, -1表示没有找到
*/
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) {
right = mid - 1; //向左继续查找
}else {
left = mid + 1; //向右继续查找
}
}
return -1;
}
}
原文:https://www.cnblogs.com/yfyyy/p/12770536.html