二分查找了解过吗?
查找思路
【a】待查找有序数组序列:1, 2, 3, 4, 5, 6, 7
起始: 定义start = 0 , end = 6, mid = (start + end ) / 2 = (0 + 6) / 2 = 3,arr[mid] = arr[3] =4
【b】假设需要查找"2", 因为2 arr[mid] = arr[3] = 4,所以需要将start移动到mid右边一 个位置,即start = mid + 1 = 4,此时重新计算mid = (start +end) / 2 = (4+ 6)/2 = 5, arr[mid] = arr[5] = 6, 因为7>arr[mid] = arr[5] = 6,所以还是需要将start移动到mid右边 一个位置,即start = mid + 1 = 5 + 1 = 6, 此时重新计算mid = (start +end) / 2 = (6 + 6) / 2 = 6.arr[6] = 7, 此时arr[mid] = arr[6] = 7,刚好等于待查找数字7,说明成功找到数字"7"所 在的位置.
【d】假设查找"0", 因为 0 < arr[mid] = arr[3] = 4, 所以需要将end移动到mid左边一个位 置,即end = mid – 1 = 3 – 1 = 2,此时重新计算mid = (start +end) / 2 = (0 + 2) / 2 = 1,arr[mid] = arr[1] = 2, 因为0 < arr[mid] = arr[1] = 2,所以需要将end移动到mid左边一个 位置,即end = mid – 1 = 1 – 1 = 0, 此时mid = (start +end) / 2 = (0 + 0) / 2 = 0,arr[mid] = arr[0] = 1,因为0 end,即start 已经大于end结束 位置,说明没有找到相应的元素0。
算法实现
public class BinarySearchUtils {
/**
* 根据指定值查找在数组中的位置
*
* @param arr 待查找有序数组
* @param value 指定值
* @return 返回值在数组中对应的下标位置
*/
public static int binarySearch(int[] arr, int value) {
//起始位置
int start = 0;
//结束位置
int end = arr.length - 1;
while (true) {
//计算中间位置下标
int mid = (start + end) / 2;
//中间值
int midValue = arr[mid];
if (value == midValue) {
return mid;
} else {
//待查找数值比中间值小,需要将
if (midValue > value) {
end = mid - 1;
} else {
//待查找数值比中间值大,需要将
start = mid + 1 start = mid + 1;
}
}
if (start > end) {
//start > end,说明未找到相应的元素,返回
-1 return -1;
}
}
}
}