二分查找

喜欢ヅ旅行 2022-04-06 14:22 336阅读 0赞

/**
    	 * 有序数组递归二分查找，定位值的下标
    	 * 
    	 * @param arr   目标数组
    	 * @param start 起始下标
    	 * @param end   末尾下标
    	 * @param key   查找的值
    	 * @return 值的下标
    	 */
    	static int binarySearch(final int[] arr, int start, int end, int key) {		
    		if (start > end || end >= arr.length) {
    			return -1;
    		}
    		/* 中间位置：(end + start) / 2 等于 (end + start) >> 1 */
    		int mid = (end + start) >> 1;
    		if (key == arr[mid]) {
    			return mid;
    		}
    		if (key > arr[mid]) {
    			start = mid + 1;
    		}
    		if (key < arr[mid]) {
    			end = mid - 1;
    		}
    		return binarySearch(arr, start, end, key);
    	}
    
    	/**
    	 * 有序数组循环二分查找，定位值的下标
    	 * 
    	 * @param arr   目标数组
    	 * @param start 起始下标
    	 * @param end   末尾下标
    	 * @param key   查找的值
    	 * @return 值的下标
    	 */
    	static int binaryWhileSearch(final int[] arr, int start, int end, int key) {
    		
    		int mid=-1;
    		do {
    			if (start > end || end >= arr.length) {
    				return -1;
    			}
    			/* 中间位置：(end + start) / 2 等于 (end + start) >> 1 */
    			mid = (end + start) >> 1;
    			if (key > arr[mid]) {
    				start = mid + 1;
    			}
    			if (key < arr[mid]) {
    				end = mid - 1;
    			}
    		} while (key != arr[mid]);
    		return mid;
    	}

发表评论取消回复

表情：

评论列表（有 0 条评论，336人围观）

还没有评论，来说两句吧...

相关阅读

相关二分查找

函数lower\_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置举例

约定不等于承诺〃/ 2022年08月07日 14:47/ 0 赞/ 50 阅读

相关二分查找

二分查找可以说是在经典不过的查找算法了，比如JAVA的库函数里，就有相应的代码实例。如下写出两个版本的二分查找，非递归和递归的非递归的 public int bi

系统管理员/ 2022年08月06日 16:24/ 0 赞/ 68 阅读

相关二分查找

//二分查找 /\ 递归算法 int searchB1(int A\[\], int low, int high, int data); 非递归算法 int

绝地灬酷狼/ 2022年05月12日 01:40/ 0 赞/ 57 阅读

相关二分查找

/ 有序数组递归二分查找，定位值的下标 @param arr 目标数组 @param start 起始下标

喜欢ヅ旅行/ 2022年04月06日 14:22/ 0 赞/ 337 阅读

相关查找——二分查找

基本思想二分查找是建立在有序顺序表基础上的！步骤如下： 1. 将表中间位置记录的关键字与给定K值进行比较，若两者相等，则查找成功。 2.

蔚落/ 2022年03月27日 03:46/ 0 赞/ 392 阅读

相关二分查找

二分查找（先排序） typedef struct LNode List; struct LNode{ ElemenType Data[MAXSIZ

爱被打了一巴掌/ 2022年02月02日 17:13/ 0 赞/ 137 阅读

相关二分查找

使用递归的版本 def bin_search(lst, num, start=None, end=None): """ 二分查找

àì夳堔傛蜴生んèń/ 2022年01月07日 04:03/ 0 赞/ 114 阅读

相关二分查找

int search2( int array\[\], int n, int v) \{ int left, right, middle;

心已赠人/ 2021年12月20日 16:07/ 0 赞/ 138 阅读

相关二分查找

二分查找二分查找是一个比较简单的算法，用 C++ 语言实现如下： template <typename T> int binary_search(

ゞ浴缸里的玫瑰/ 2021年12月13日 03:57/ 0 赞/ 203 阅读

相关二分查找

> 一、自己实现的 include<iostream> include<cstdio> include<algorithm> u

左手的ㄟ右手/ 2021年09月21日 17:12/ 0 赞/ 309 阅读