最近在B站上看左神的视频学习算法，视频地址，b站上搜索《一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教程》，为了督促自己学习，开个合集记录一下每天的学习和练习历程。 二分查找算法（Binary Search），也称为二分法或折半查找，是一种用于在有序数组中查找目标值位置的搜索算法。它通过反复将可能包含目标值的数组部分二分为两半，直到找到目标值或将搜索缩小到一个空子数组为止。它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

题目一 在一个有序数组中，找某个数是否存在（经典二分查找）1、代码

public static boolean exist(int[] arr, int num) {        if (arr == null || arr.length == 0) {            return false;        }        int left = 0;        int right = arr.length - 1;        int mid = 0;        while (left < right) {            mid = left + ((right - left) >> 1); // mid = (left + right) / 2            if (arr[mid] == num) {                return true;            } else if (arr[mid] > num) {                right = mid - 1;            } else {                left = mid + 1;            }        }        return arr[left] == num;    }

2、测试代码

public static void main(String[] args) {        int[] arr = {1, 3, 5, 7, 9};        System.out.println(exist(arr, 3));        System.out.println(exist(arr, 4));    }

3、测试结果

数字3被成功找到、数字4未被找到

truefalse

题目二 在一个有序数组中，找>=某个数最左侧的位置1、代码

public static int nearLeftestIndex(int[] arr, int value) {        int left = 0;        int right = arr.length - 1;        int index = -1; // 记录最左的对号        while (left <= right) {            int mid = left + ((right - left) >> 1);            if (arr[mid] >= value) {                index = mid;                right = mid - 1;            } else {                left = mid + 1;            }        }        return index;    }

2、测试代码

public static void main(String[] args) {        int[] arr = {1, 2, 3, 3, 3, 4, 5, 6, 7};        System.out.println(nearLeftestIndex(arr, 3));    }

3、测试结果

找到下标为2的数字3

2

题目三 在一个有序数组中，找<=某个数最右侧的位置1、代码

public static int nearRightestIndex(int[] arr, int value) {        int left = 0;        int right = arr.length - 1;        int index = -1; // 记录最右的对号        while (left <= right) {            int mid = left + ((right - left) >> 1);            if (arr[mid] <= value) {                index = mid;                left = mid + 1;            } else {                right = mid - 1;            }        }        return index;    }

2、测试代码

public static void testNearRight(){        int[] arr = {1, 2, 3, 3, 3, 4, 5, 6, 7};        System.out.println(nearRightestIndex(arr, 3));    }

3、测试结果

找到下标为4的数字3

4

题目四 局部最小值问题1、代码

public static int getLessIndex(int[] arr) {        if (arr == null || arr.length == 0) {            return -1; // no exist        }        if (arr.length == 1 || arr[0] < arr[1]) {            return 0;        }        if (arr[arr.length - 1] < arr[arr.length - 2]) {            return arr.length - 1;        }        int left = 1;        int right = arr.length - 2;        int mid = 0;        while (left < right) {            mid = (left + right) / 2;            if (arr[mid] > arr[mid - 1]) {                right = mid - 1;            } else if (arr[mid] > arr[mid + 1]) {                left = mid + 1;            } else {                return mid;            }        }        return left;    }

2、测试代码

public static void main(String[] args) {        int[] arr = { 6, 5, 3, 4, 6, 7, 8 };        System.out.println(getLessIndex(arr));    }

3、测试结果

找到下标为2的数组中的最小数字3

2