算法之二分查找法
需求描述:
在有序数组A内,查找值target
如果找到返回索引
如果找不到返回-1
算法实现描述
前提条件:给定一个含有n个元素的有序数组A,满足A0≤A1≤A2≤···An-1,一个待查值target
实现步骤: 1、创建i = 0, j = n - 1;
2、如果i > j,结果查找,没找到
3、设置m = floor((i+j) / 2),m为中间索引,floor是向下取整(≤(i + j) / 2的最小整数)
4、如果target < Am 设置 j = m - 1,跳到第二步
5、如果Am < target 设置 i = m + 1, 跳到第二步
6、如果Am = target,结束查找,找到了
代码实现
/***
* 二分查找法实现
* @param args 数据
* @param target 查找目标
* @return 找到返回索引
* 找不到返回-1
*/
public static int binarySearchBasic(int[] args, int target) {
int i = 0, j = args.length - 1;//设置指针和初始值
while (i <= j) {//范围内有东西
int m = (i + j) / 2;
if (target < args[m]) {//目标在左边
j = m-1;
} else if (args[m] < target){//目标在右边
i = m + 1;
} else {
return m;//找到数据的id
}
}
return -1;
}