704. 二分查找
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return-1.
You must write an algorithm withO(log n)runtime complexity.
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
#1 自己看到题目的第一想法
搜索题，暴力解法的话就是把nums循环一遍。但是由于题目中有要求 runtime complexity 为O(log n) 并且数组是有序的，因此这是一道典型的二分搜索题。
var search = function(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
let mid = Math.ceil((left + right) / 2);
if (nums[mid] === target) {
return mid
} else if (nums[mid] > target) {
right = mid - 1
} else {
left = mid + 1
}
}
return -1
};
#2 看完代码随想录之后的想法
数组中一旦有重复元素，使用二分查找法返回的元素下标就可能不是唯一的了。
二分搜索另一个重要的点的边界条件，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)，这两种区间的定义的写法也是完全不同的。
个人习惯使用左闭右闭即[left, right]，在这种情况下，一定需要 right = mid - 1 以及 left = mid + 1，否则就有可能会陷入死循环。
#3 收获
对二分搜索的边界条件有了更深的理解。二分搜索的时间复杂度是 logn
#4 类似题目
类似的题目有 35. Search Insert Position - 重点在于推导出最终 return 的是 left 而非 right 或者是 mid
34. Find First and Last Position of Element in Sorted Array 也是类似题，用两个双循环即可实现。尽管34题中target是可能多次在array中出现，但是我们仍然可以用二分搜索来解决，突破点在于如果 nums[mid] === target 时如何移动 left / right。如果我们想得到第一个出现的target值，那么我们就需要使得 right = mid - 1 从而去寻找第一个出现target值的index。 同理，如果为了得到最后一个出现的target值，那么则需要 left = mid + 1。
69. Sqrt(x) 用二分搜索也可以解决，注意点是return right。因为 left = right + 1，right小于left的。367. Valid Perfect Square 几乎一样的思路。
27. 移除元素
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
#1 自己看到题目的第一想法
看这个题目的第一眼我其实是完全没有想到双指针。我的想法是新建一个变量index，然后再循环array中的每一个元素elem，如果elem != val，那么把 elem 赋值给elem[index] 同时 index++。
#2 看完代码随想录之后的想法
我自己的思路其实是正确的，但是自己当时没有意识到这也是双指针的一种。本题所使用的双指针法不同于之前的left和right双指针，本题所用的双指针是通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。我在#1中所写的index就是慢指针，遍历array的时候就是快指针。
#3 收获
对双指针有了更深的理解。双指针通过把两个for循环降为一个for循环，成功的把时间复杂度降到了n。
针对remove / delete 同时维持order 和 without copying an array的题目可以考虑采取快慢双指针。
#4 类似题目
26. Remove Duplicates from Sorted Array 和 283. Move Zeroes 与27题都几乎一摸一样。
844.比较含退格的字符串 和 977.有序数组的平方 也类似
