704. 二分查找
二分查找理论
二分查找是一个时间效率极高的算法，尤其是面对大量的数据时，其查找效率是极高，时间复杂度是log(n)。主要思想就是不断的对半折叠，每次查找都能除去一半的数据量，直到最后将所有不符合条件的结果都去除，只剩下一个符合条件的结果。
二分查找需要的条件
- 用于查找的内容逻辑上来说是需要有序的
- 查找的数量只能是一个，而不是多个
因为查找的区间是不断迭代的，所以确定查找的范围十分重要，主要就是左右区间的开和闭的问题，开闭不一样，对应的迭代方式也不一样，有以下两种方式：
左闭右闭
[left, right]
左闭右开[left, right)
左闭右闭
1 class Solution {
2 public int search(int[] nums, int target) {
3 if(target<nums[0]||target>nums[nums.length-1]){
4 return -1;
5 }
6 int left = 0;
7 int right = nums.length-1;
8 while(left<=right){
9 int middle = left + ((right-left)/2);
10 if(nums[middle]>target){
11 right = middle - 1;
12 }else if(nums[middle]<target){
13 left = left + 1;
14 }else{
15 return middle;
16 }
17 }
18 return -1;
19 }
20 }
左闭右开
1 class Solution {
2 public int search (int[] nums,int target){
3 if(target<nums[0]||target>nums[nums.length-1]){
4 return -1;
5 }
6 int left = 0;
7 int right = nums.length-1;
8 while (left < right) {
9 int middle = left + ((right - left) / 2);
10 if (nums[middle] > target) {
11 right = middle;
12 } else if (nums[middle] < target) {
13 left = middle + 1;
14 } else {
15 return middle;
16 }
17 }
18 return -1;
19 }
20
同类题 35.搜索插入位置
1 class Solution {
2 public int searchInsert(int[] nums, int target) {
3 if(nums[0]>target){
4 return 0;
5 }else if (nums[nums.length-1]<target){
6 return nums.length;
7 }else {
8 int left = 0;
9 int n =0;
10 int right = nums.length-1;
11 while(left<=right){
12 int middle = left + ((right -left)/2);
13 if(target>nums[middle]){
14 left = middle + 1;
15 }else if (target<nums[middle]){
16 right = middle - 1;
17 }else
18 return middle;
19 }
20 return right+1;}
21 }
22 }
难点：最后为什么是return right+1;
原因：当不再进入while里面的时候一定是right<left.而且此时数组里面也匹配不到与target相等的数。所以它要插入的位置一定是此时left 和right之间。但更小的是right，所以插入的位置就在right+1.
27. 移除元素思路：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作
- 快指针:寻找 新数组(不含目标元素) 中的元素
- 慢指针:指向更新新数组下标的位置,等待加入快指针找到符合要求的数
1 class Solution {
2 public int removeElement(int[] nums, int val) {
3 int slowIndex = 0;
4 for(int fastIndex = 0; fastIndex < nums.length; fastIndex++){
5 if(nums[fastIndex]!=val){
6 nums[slowIndex++]=nums[fastIndex];
7 }
8 }
9 return slowIndex;
10 }
11 }
标签：27,nums,704,middle,int,right,移除,查找,left From： https://www.cnblogs.com/adelall/p/17429895.html