最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

时讯：二分法

来源：博客园


(资料图片仅供参考)

二分法

二分法多用于有序数组，经典的案例是查找一个一个有序数组中是否存在某个数

题目1 :找出一个有序数组中是否存在某个数？

public static boolean exist(int[] sortedArr, int num) {        if (sortedArr == null || sortedArr.length == 0) {            return false;        }        int L = 0;        int R = sortedArr.length - 1;        int mid = 0;        // L..R        while (L < R) {            mid = L + ((R - L) >> 1); // 相当于 mid = (L + R) / 2 ，面对大数时更安全，不容易溢出            if (sortedArr[mid] == num) {                return true;            } else if (sortedArr[mid] > num) {                R = mid - 1;            } else {                L = mid + 1;            }        }        return sortedArr[L] == num;    }

题目2：在有序数组中找出>=value 的最左位置

例如 [1,1,2,2,2,2,2,3,3,3,4,4,4],>=2的最左位置即下标2

// 在arr上，找满足>=value的最左位置    public static int nearestIndex(int[] arr, int value) {        int L = 0;        int R = arr.length - 1;        int index = -1; // 记录最左的对号        while (L <= R) {            int mid = L + ((R - L) >> 1);            if (arr[mid] >= value) {                index = mid;                R = mid - 1;            } else {                L = mid + 1;            }        }        return index;    }

题目3：在有序数组中找出<=value的最右位置

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

题目4：找出一个无序数组中的相对最小

//找出相对最小    public static int getLessIndex(int[] arr) {        if (arr == null || arr.length == 0) {            return -1; // no exist        }        if (arr.length == 1 || arr[0] < arr[1]) {  //判断0位置是否时相对最小            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;    }

关键词： 最左位置 是否存在 一个一个