5 минут, чтобы показать вам: почему написание бинарного поиска делает интервьюируемого таким несчастным?

JavaScript

Бинарный поиск можно назвать одним из самых простых и простых для понимания алгоритмов среди всех алгоритмов, но на самом деле это также один из экзаменационных вопросов с самым высоким процентом сдачи.Собеседования свежих выпускников различных крупных компаний , такие оценки не редкость: говорить о проектах Когда я пришел поболтать ну я попросил его написать бинарный поиск но не смог написать. Я не буду это комментировать.Что касается бинарного поиска, то я думаю, что это не так просто, как все думают.Уместнее всего описать его как "идея очень проста, а детали - черт". Если вы не верите мне, давайте посмотрим на это шаг за шагом.

Сложность: граничное определение

Код бинарного поиска примерно такой:

let binarySearch = (arr, target) => {
    let begin = 0;
    let end = ???;
    while(???) {
        int mid = begin + (end -begin) / 2;
        if(arr[mid] == target) {}
        else if(arr[mid] > target) {}
        else if(arr[mid] < target) {}
    }
    return ???;
}

Видно, что проблема уже очевидна: когда много людей не подготовлены, базовый фреймворк можно написать, но граничные условия были неясны, что приводит к эмоциональному напряжению, растерянности и в итоге ничего.

Теперь давайте разберем различные граничные условия,

let search = (arr, target) => {
    let begin = 0;
    let end = arr.length-1; //写成这样，相当于搜索区间为[begin, end]，这是一个闭区间
    while(begin <= end) {//重点: 因为闭区间，所以到了begin等于end时，其实区间内还有一个值要判断，
                         //因此只有begin>end的时候才能停止
        let mid = (begin + end) >>> 1;//位运算，无符号右移一位，同Math.floor((begin+end)/2)
        if(arr[mid] == target) {
            return mid;
        }
        else if(arr[mid] > target) {
            end = mid - 1;//因为是闭区间，搜索范围变为[left, mid - 1]
        }
        else if(arr[mid] < target) {
            begin = mid + 1; //搜索范围变成[mid + 1, end]
        }
    }
    return -1;
}

На самом деле, мы также можем сделать это:

let search = (arr, target) => {
    let begin = 0;
    let end = arr.length; //写成这样，相当于搜索区间为[begin, end)，这是一个前闭后开的区间
    while(begin < end) {//重点:
                       //因为前闭后开的区间，所以到了begin等于end时，其实区间内已经没有值了，直接停止
        let mid = (begin + end) >>> 1;
        if(arr[mid] == target) {
            return mid;
        }
        else if(arr[mid] > target) {
            end = mid;//因为是闭区间，搜索范围变为[left, mid - 1]
        }
        else if(arr[mid] < target) {
            begin = mid + 1; //搜索范围变成[mid + 1, end]
        }
    }
    return -1;
}

Я думаю, что комментарии были объяснены достаточно ясно, и я надеюсь, что каждый сможет понять принцип интервальной оценки, вместо того, чтобы слепо запоминать код.

Кстати, согласно вышеизложенной идее, мы можем написать это и рекурсивно:

let search = (nums, target) => {
    let helpSearch = (nums, begin, end, target) => {
      if(begin > end) return -1;
      let mid = (begin + end) >>> 1;
      if(nums[mid] == target) return mid;
      else if(nums[mid] > target) 
        return helpSearch(nums, begin, mid - 1, target);
      else 
        return helpSearch(nums, mid+1, end, target);
    }
    //闭区间形式
    return helpSearch(nums, 0,  nums.length - 1, target);
}

let search = (nums, target) => {
    let helpSearch = (nums, begin, end, target) => {
      if(begin >= end) return -1;
      let mid = (begin + end) >>> 1;
      if(nums[mid] == target) return mid;
      else if(nums[mid] > target) 
        return helpSearch(nums, begin, mid, target);
      else 
        return helpSearch(nums, mid+1, end, target);
    }
    //前闭后开区间形式
    return helpSearch(nums, 0,  nums.length, target);
}

Трудности 2: целевое значение повторяется

Просто посмотрите на реальный вопрос:

Временная сложность уровня O(log n), грубо говоря, представляет собой бинарный поиск, то есть нам нужно использовать бинарный поиск, чтобы найти крайнюю левую позицию и крайнюю правую позицию целевого значения, на самом деле есть еще какие-то сложности.

Давайте разберем его шаг за шагом.

Найдите положение левой границы

let left = 0;
let mid;
let right = nums.length;
while(left < right) {
  mid = (left + right) >>> 1;
  if (nums[mid] > target) {
      right = mid;
  } else if (nums[mid] < target) {
      left = mid + 1;
  } else if (nums[mid] == target) {
      right = mid; //重点
  }
}
//分析:目前的nums[left]一定是大于等于target的值
if (left == nums.length) return -1;
else return nums[left] == target ? left : -1;

найти правильное положение границы

let left = 0; 
let right = nums.length;
while(left < right) {
  mid = (left + right) >>> 1;
  if (nums[mid] > target) {
      right = mid;
  } else if (nums[mid] < target) {
      left = mid + 1;
  } else if (nums[mid] == target) {
      left = mid + 1; //注意
  }
}
//分析: 目前的nums[left]左边的部分都是大于等于target的部分，因此我们取nums[left - 1]
if (left == 0) return -1;
else return nums[left - 1] == target ? left - 1: -1;

Конечно, здесь я использую фронт-закрытый и задний-открытый интервалы, вы также можете использовать закрытый интервал напрямую.

окончательный код показать

var searchRange = function(nums, target) {
  let left = 0;
  let mid;
  let right = nums.length;
  while(left < right) {
      mid = (left + right) >>> 1;
      if (nums[mid] > target) {
          right = mid;
      } else if (nums[mid] < target) {
          left = mid + 1;
      } else if (nums[mid] == target) {
          right = mid;
      }
  }
  let leftIndex = -1, rightIndex = -1;
  if (left == nums.length) return [-1, -1];
  else leftIndex = nums[left] == target ? left : -1;

  left = 0; right = nums.length;
  while(left < right) {
      mid = (left + right) >>> 1;
      if (nums[mid] > target) {
          right = mid;
      } else if (nums[mid] < target) {
          left = mid + 1;
      } else if (nums[mid] == target) {
          left = mid + 1;
      }
  }
  if (left == 0) return [-1, -1];
  else rightIndex = nums[left - 1] == target ? left - 1: -1;
  
  return [leftIndex, rightIndex];
};

В общем, бинарный поиск действительно нетрудно думать, но необходимо очень четко понимать смысл интервала, представляемого граничной переменной, чтобы мышление не было беспорядочным.

Категории