本文共 1266 字,大约阅读时间需要 4 分钟。
二分查找(折半查找),是一种在有序数组中查找特定元素的搜索算法。
查找过程可以分为以下步骤:
(1)首先,从有序数组的中间的元素开始搜索,如果该元素正好是目标元素(即要查找的元素),则搜索过程结束,否则进行下一步。
(2)如果目标元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半区域查找,然后重复第一步的操作。 (3)如果某一步数组为空,则表示找不到目标元素。// 非递归算法function binary_search1(nums, target) { var left = 0; var right = nums.length-1; while(left <= right) { //var mid = left + parseInt((right - left) / 2); var mid = Math.floor((left + right) / 2); if(target == nums[mid]){ return mid; }else if(target < nums[mid]){ right = mid - 1; }else{ left = mid + 1; } } return -1;}var arr = [1,2,3,4,5,6,7,8,9,10,11,23,44,86];var result = binary_search1(arr, 10);console.log(result); // 9 返回目标元素的索引值
// 递归算法function binary_search2(nums, low, high, target) { if(low > high) { return -1; } var mid = Math.floor((low + high) / 2); if (target == nums[mid]) { return mid; }else if (target < nums[mid]) { high = mid - 1; return binary_search2(nums, low, high, target); }else { low = mid + 1; return binary_search2(nums, low, high, target); }}var arr = [1,2,3,4,5,6,7,8,9,10,11,23,44,86];var result = binary_search2(arr, 0, arr.length, 10);console.log(result); // 9 返回目标元素的索引值
转载地址:http://knuvi.baihongyu.com/