Java递归和非递归二分查找

矫情吗；* 2022-02-02 04:49 277阅读 0赞

**非递归实现二分查找**

/** * 非递归查找key * @param array * @param key * @return */
    	public static int binarySearch(int[] array, int key) { 
    		bubbleSort(array);
    		int left = 0;
    		int right = array.length - 1;
    		int mid;
    		while (left <= right) { 
    			mid = (left + right) / 2;
    			if (array[mid] == key) { 
    				return mid + 1;
    			} else if (array[mid] < key) { 
    				left = mid + 1;
    			} else { 
    				right = mid - 1;
    			}
    		}
    		return -1;
    	}

**递归实现二分查找**

/** * 递归查找key * * @param array * @param key * @param left * @param right * @return */
    	public static int sort(int[] array, int key, int left, int right) { 
    		if (left <= right) { 
    			int mid = left + right;
    			if (key == array[mid]) { 
    				return mid + 1;
    			} else if (key < array[mid]) { 
    				return sort(array, key, left, mid - 1);
    			} else { 
    				return sort(array, key, mid + 1, right);
    			}
    
    		}
    		return -1;
    	}

**查询第一个出现元素的位置**

/** * 查询第一个元素出现的位置 * * @param array * @param key * @return */
    	public static int biSearchFirst(int[] array, int key) { 
    		int len = array.length;
    		int left = 0;
    		int right = len - 1;
    		int mid = 0;
    		while (left < right) { 
    			mid = (left + right) >> 1;
    			if (array[mid] < key) { 
    				left = mid + 1;
    			} else { 
    				right = mid;
    			}
    		}
    		if (array[left] != key) { 
    			return -1;
    		} else { 
    			return left;
    		}
    	}

**查询最后一个出现元素的位置**

/** * 查询元素最后一次出现的位置 * * @param array * @param key * @return */
    	public static int biSearchLast(int[] array, int key) { 
    		int len = array.length;
    		int left = 0;
    		int right = len - 1;
    		int mid = 0;
    		while (left < right) { 
    			mid = (left + right + 1) >> 1;
    			if (array[mid] <= key) { 
    				left = mid;
    			} else { 
    				right = mid - 1;
    			}
    		}
    		if (array[left] != key) { 
    			return -1;
    		} else { 
    			return right;
    		}
    	}