记一个二分查找的算法模板(Java版)
程序员文章站
2024-03-20 17:14:46
...
先上代码
public int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0)
return -1;
int start = 0, end = nums.length - 1, mid;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (target <= nums[mid])
end = mid;
else
start = mid;
}
if (nums[start] == target)
return start;
if (nums[end] == target)
return end;
return -1;
}
注意:
- 为什么mid = start + (end - start) / 2;而不是mid = (start + end) / 2;是为了防止内存溢出。
- 根据不同的题目要求,可以改写方法体,比如是返回第一个出现的target还是返回最后一个出现的target;返回第一个则如下图所示:
返回最后一个则如下图所示:
- 为什么不是end = mid ++和start = mid ++;因为题目有可能会要求返回第一个比target大的数值的下标或者第一个比target小的数值下标之类的问题,如果是返回等于target的下标则可以。
- 为什么while判断条件是start + 1 < end而不是start < end;因为可能会出现死循环,比如start = 1,end = 2,mid = (1 + 2) / 2 =1;然后如果进入到了start = mid,则start和end一直保持不变,程序将会进入死循环中。
上一篇: IOS runtime动态运行时一
下一篇: ios - Runtime 运行时机制