重开之数据结构(二刷)

引言:
由于前段时间学习效率不高,导致后面复习前面数据结构没有一个大纲,因此打算重新来学习以下数据结构,期望再次把数据结构学透,并有深刻的印象.并且记录每一次的学习记录以便于后续复习

二分查找

需求:在有序数组arr内,查找target值

如果找到返回索引位置
如果找不到返回 -1

基础版

步骤:

设定两个指针(左闭右闭) 分别为 i= 0,j = arr.length-1
循环条件 i<j ,如果i>j 结束查找没找到
定义变量 m = (i+j)/2
比较target与m索引的值
(1)target < arr[m] —> j = m-1
(2)target > arr[m] —> i = m+1
(3)target = arr[m] —> return m
循环结束没找到返回-1;

public static int binarySearch(int[] arr,int target){
        int i = 0,j = arr.length-1;//设置指针和初始值
        while(i<=j){
            int m = (i+j)/2;
            if(target<arr[m]){
                j = m-1;
            }else if(arr[m]<target){
                i = m+1;
            }else{
                return m;
            }
        }
        return -1;
    }

查找14动态演示
在这里插入图片描述

问题一: 循环条件为i<=j 为什么不是i<j?

相当于多了i=j 这个条件 ,意味着但i=j 时这个元素也要参与比较
比如查找 5 时最后 i j m 都会指向5 若没有= 就跳出了循环i,j
就没有参与到比较

请添加图片描述
问题二: (i+j) /2 是否有问题?

从客观来讲,没有问题但是在极端情况下,数据量达到整型的最大值的(i+j)就会出现问题由于计算机存储的数据是有一定的范围的,就有可能会导致算出来的结果为负值所以要用到位运输 (i+j)>>>1 无符号右移可以避免此情况发生

在这里插入图片描述
问题三:若在有序数组中存在相同的元素该如何找到目标元素的首位置或者最后一个位置?

只需在基础版的else上优化一下即可

改动版

思维逻辑大概与基础版相似考虑在算法的优劣这种方法相当于基础版更优化了一些

   public static int binarySearchAlternative(int[] arr,int target){
        int i = 0,j = arr.length;
        //变化一:i 作为查找数据的左闭  而j 只是一个边界不参与运输
        while (i<j){
        //i<j 表示 j下标的运算不用参与计算了
            int m = (i+j)>>>1;
            if (target<arr[m]){
                j = m;
                //j始终保持为边界
            } else if (arr[m]<target) {
                i = m+1
            }else{
                return m;
            }
        }
        return -1;
    }

平衡版

在基础版中假设在while 循环中执行了L次 ,那么假设目标元素在最左边 if 就执行L次,而如果元素在最右边,if-else 就执行了2*L次因此用该方法查找时并不平衡.

public static int binarySearchBalance(int[] arr,int target){
        int i = 0,j = arr.length;
        while(1<j-i){
            int m = (j+i)>>>1;
            if(target<arr[m]){
                j = m;
            }else {
                i = m;
            }

        }
        if(arr[i] == target){
            return i;
        }else {
            return -1;
        }
    }