《JavaScript算法》二分查找的思路与代码实现
2024-09-07 04:07:27
二分查找的思路
- 首先,从有序数组的中间的元素开始搜索,如果该元素正好是目标元素(即要查找的元素),则搜索过程结束,否则进行下一步。
- 如果目标元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半区域查找,然后重复第一步的操作。
- 如果某一步数组为空,则表示找不到目标元素
代码实现
- 非递归实现
// 非递归算法
function binary_search(arr, key) {
let low = 0;
let high = arr.length - 1;
while(low <= high){
let mid = parseInt((high + low) / 2);
if(key === arr[mid]){
return mid;
}else if(key > arr[mid]){
low = mid + 1;
}else if(key < arr[mid]){
high = mid -1;
}else{
return -1;
}
}
}
- 递归实现
// 递归算法
function binary_search(arr,low, high, key) {
if (low > high){
return -1;
}
let mid = parseInt((high + low) / 2);
if(arr[mid] === key){
return mid;
}else if (arr[mid] > key){
high = mid - 1;
return binary_search(arr, low, high, key);
}else if (arr[mid] < key){
low = mid + 1;
return binary_search(arr, low, high, key);
}
};
原文链接:https://github.com/qianbin01/frontend_train#sort
最新文章
- word域2
- day26_网络编程第一天
- UVa 11889 Benefit(数论)
- iOS10适配及Xcode8配置
- [OpenCV] Image Processing - Grayscale Transform
- HTML 5:你必须知道的data属性
- Vim及VimScript资料总结《转载》
- 如何删除chrome地址栏里面曾经输错的地址
- [asp.net mvc 奇淫巧技] 06 - 也许你的项目同一个用户的请求都是同步的
- fastadmin模态框(弹出框)
- 八大排序算法——堆排序(动图演示 思路分析 实例代码java 复杂度分析)
- Luogu1627 [CQOI2009]中位数
- 跨平台桌面程序框架Electron
- [转载]Javascript .then()这个方法是什么意思?
- FileZilla建立服务器,命令行客户端
- stopPropagation()阻止事件的冒泡传递
- django POST表单的使用
- TCHAR函数查询
- 12 extremely useful hacks for JavaScript
- sql server字符串的类型