【数据结构与算法】—— 二分查找
文章目录
- 二分查找的概念 二分查找指的是在排好序的数组中,找到目标元素。如果元素存在则返回元素的下标,不存在则返回-1. 下面以升序为例进行简单描述
- 查找过程: 取数组中间元素与查找元素target比较。如果target等于中间元素则直接返回中间元素的下标,如果target小于数组中间元素则在数组左边查找,如果target大于数组中间元素则在右边查找。重复以上步骤。
- 二分查找的时间复杂度 O(logn)
- Java实现
- 1 迭代版本
public int searchByLoop(int[] arr, int target) { return searchByLoop(arr, 0, arr.length - 1, target); }
private int searchByLoop(int[] arr, int low, int high, int target) { while (low <= high) { int mid = (low + high) / 2; if (target == arr[mid]) { return mid; } else if (target < arr[mid]) { high = mid - 1; } else { low = mid + 1; } } return -1; }
4.2 递归版本public int searchByRecursion(int[] arr, int target) { return searchByRecursion(arr, 0, arr.length - 1, target); }
private int searchByRecursion(int[] arr, int low, int high, int target) { int mid = (low + high) / 2; if (target == arr[mid]) { return mid; } if (low > high) { return -1; } if (target < arr[mid]) { return searchByRecursion(arr, low, mid - 1, target); } return searchByRecursion(arr, mid + 1, high, target); }
``` 5. 数据结构系列代码地址 Github:https://github.com/bennetty74...
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册⭐️ Admin快速开发: https://show.cool-admin.com/
赞 0⭐️ 官方文档: https://cool-js.com
赞 0⭐️ chatgpt在线体验: https://cool-js.com/ai/chat-vip/index.html?r=helloworld
赞 0