day01【704. 二分查找，35.搜索插入位置，27. 移除元素】-526互联

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 }