您现在的位置是:首页 > Javascript
当前栏目
二分法
2023-04-18 12:37:23 时间
二分法
二分法多用于有序数组,经典的案例是查找一个一个有序数组中是否存在某个数
题目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; }
相关文章
- Vue3路由配置createRouter、createWebHistory、useRouter,useRoute
- Vue3中的watch监听
- 微信小程序自定义组件(超详细)
- vue中 router.beforeEach() 的用法
- 手把手教你在 Vue3 中自定义指令
- 前端JS也可以连点成线(Vue中运用 AntVG6)
- 【React】react-router 路由详解
- vue获取当前页面地址
- 【面试题】2023年最新前端面试题-react篇
- vue3 hooks使用
- npm install 报错(npm ERR! code EPERM npm ERR! syscall mkdir npm ERR! path D:\node.js\odejs)
- 后端必会的前端vue基础知识
- JS 连接MQTT的方法(mqtt.js的使用方法)
- 如何使用vue-cli来搭建vue项目?详细步骤跟着我来吧!
- UNI-APP 人脸识别分析及实现(前端)
- uniapp引入模块化js文件和非模块化js文件
- vue项目国际化(使用vue-i18n)
- (详解)Vue设置select下拉框的默认选项(解决select空白的bug)
- Nodejs安装及npm配置(超详细)
- vue路由配置