首页 > 代码库 > binary-search
binary-search
For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity. If the target number does not exist in the array, return -1.
Example If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.
题解
题目的意思是,找到target在array中第一次出现的位置。
var postion = function (arr, target) { if (arr.length === 0) { return -1; }
var start = 0; var end = arr.length - 1; var mid; // 判断条件为 start+1<end 可避免死循环 while (start + 1 < end) { mid = start + Math.floor((end - start) / 2); //找target第一次出现的位置,因此不能在此时返回mid,且需要 end=mid; 如果找target最后一次出现的位置,则start = mid; if (arr[mid] === target) { end = mid; } else if (arr[mid] < target) { start = mid; } else if (arr[mid] > target){ end = mid; } } //如果要返回target第一次出现的位置,则先比较arr[start]; 如果要返回target最后一次出现的位置,则先比较arr[end]; if (arr[start] === target) { return start; } if (arr[end] === target) { return end; } return -1; };
key point:
1. while判断条件使用(start + 1 < end),避免死循环
2. 求mid时使用 start+(end-start)/2 而不是 (start+end)/2 ,因为第一种写法可避免start太大时溢出
3. while循环结束后再判断 arr[start] arr[end] ? target,根据求first postion 还是 last position确定判断次序
binary-search
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。