首页 > 代码库 > 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