Leetcode 704.二分查找

题目：704. 二分查找

初始思路

标准的二分查找，题目已经升序排列好元素。
先定义好初始区间，当中值小于目标值时，转移到右半区间查找，反之转移到左半区间查找。
找到的话就返回mid值，找不到的话就返回-1

代码

  1. // 第一种：定义 target 是在一个在左闭右闭的区间里，也就是[left, right] 
  2. var search = function (nums, target) {
  3.     let left = 0
  4.     let right = nums.length - 1
  5.     while (left <= right) {
  6.         // let mid = Math.floor((left + right) / 2)
  7.         let mid = Math.floor(left + ((right - left) / 2)) // 防止left+right加起来溢出
  8.         if (nums[mid] < target) {
  9.             left = mid + 1
  10.         } else if (nums[mid] > target) {
  11.             right = mid - 1
  12.         } else {
  13.             return mid
  14.         }
  15.     }
  16.     return -1
  17. };
  1. // 第二种：定义 target 是在一个在左闭右开的区间里，也就是[left, right)
  2. var search = function (nums, target) {
  3.     let left = 0
  4.     let right = nums.length // 因为右边是开区间所以不用-1
  5.     while (left < right) {
  6.         let mid = Math.floor(left + ((right - left) / 2))
  7.         if (nums[mid] > target) {
  8.             // target 在左区间，在[left, middle)中
  9.             right = mid
  10.         } else if (nums[mid] < target) {
  11.             // target 在右区间，在[middle + 1, right)中
  12.             left = mid + 1
  13.         } else {
  14.             return mid
  15.         }
  16.     }
  17.     return -1
  18. }

感想

  1. 一开始总是调试不成功，后来发现是mid的问题，除了之后变成了小数，需要用floor方法向下取整，是JS语言特有问题。
  2. 同时也要注意while里面条件的判断，是否要带等于符号。
  3. 之前一直写的都是第一种方法（左右都闭）的方法，今天补充了第二种写法（左闭右开）。

Leetcode 27.移除元素

题目：27. 移除元素

初始思路

因为之前写过一部分题目，第一反应就是使用双指针，但是想法仍然是后一个元素覆盖前一个元素，没有领悟到双指针的精髓，写起来还是错的。

代码

  1. // 暴力解法
  2. var removeElement = function (nums, val) {
  3.     let n = nums.length
  4.     for (let i = 0; i < n; i++) {
  5.         if (nums[i] == val) {
  6.             for (let j = i + 1; j < n; j++) {
  7.                 nums[j - 1] = nums[j]
  8.             }
  9.             i--
  10.             n--
  11.         }
  12.     }
  13.     return n
  14. }
  1. // 双指针写法
  2. var removeElement = function (nums, val) {
  3.     let left = 0
  4.     for (let right = 0; right < nums.length; right++) {
  5.         // right遍历整个数组，当与val不相等的时候赋值，并移动Left指针
  6.         // 如果相等的话就不移动left指针
  7.         if (nums[right] != val) {
  8.             nums[left] = nums[right]
  9.             left++
  10.         }
  11.     }
  12.     return left
  13. }

感想

  1. 还是首先掌握暴力解法，当双指针解法卡壳的时候首先还是要用暴力解法做出来。
  2. 双指针解法中：right指针用于遍历整个数组元素，用来查找是否与val相等。

当right指针所对应的值不是val时，就用left指针更新数组。
如果right指针所对应的值是val，right指针继续向后查找，left指针留在原地，等待下次更新。

  1. 要多多练习双指针的题目，理解双指针的思想。