首页 > 代码库 > 数据结构——二分搜索
数据结构——二分搜索
递归实现
/** * 二分搜索(递归实现) * @param A 待搜索数组 * @param num 搜索值 * @param left 区间左指针 * @param right 区间右指针 * @param mid 基准 */private static void search(int[] A, int num, int left, int right, int mid) { if (A[mid] == num) { // 如果找到要找的数,记录其下标 res = mid; } if (left >= right) return ; if (A[mid] >= num) { // 出现在左边 right = mid - 1; mid = left + (right-left)/2; search(A, num, left, right, mid); } if (A[mid] < num) { // 出现在右边 left = mid + 1; mid = left + (right-left)/2; search(A, num, left, right, mid); }}
非递归实现
/** * 二分搜索(非递归实现) * @param A 带搜索数组 * @param n 数组长度 * @param num 搜索值 * @return */private static int search2(int[] A, int n, int num) { int left = 0; int right = n - 1; int res = -1; while (left <= right) { int mid = left + (right - left)/2; if (A[mid] == num) { res = mid; right = mid - 1; } if (A[mid] >= num) { // 左区间 right = mid - 1; } else { left = mid + 1; } } return res;}private static int search3(int[] arr, int n, int num) { int left = 0; int right = n-1; while (left <= right) { int mid = left + ((right-left)>>1); if (arr[mid] > num) { right = mid-1; }else if (arr[mid] < num) { left = mid+1; }else { return mid; } } return -1;}
数据结构——二分搜索
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。