關于二分查找及變體

/********************************************* All Rights Reserved By www.laughing.ren* @author:Laughing_Lz* @version:2018年11月22日 下午11:28:28* ******************************************/ package ren.laughing.code.Test;import java.util.Arrays;public class Search {/*** 簡單的二分查找，前提是數組是有序，且無重復值* * @param arr arr*/public static int binarySearch(int value, int[] arr) {int low = 0, high = arr.length - 1, middle;// 為什么要是<=呢？while (low <= high) {middle = low + ((high - low) >> 1);if (arr[middle] < value) {low = middle + 1;} else if (arr[middle] > value) {high = middle - 1;} else {return middle;}}return -1;}/*** 遞歸方法實現簡單二分查找，前提同上：數組有序，且無重復值* * @param value value* @param arr arr* @param low low* @param high high* @return*/public static int recursionBinarySearch(int value, int[] arr, int low, int high) {if (low > high) {return -1;}int middle = low + ((high - low) >> 1);if (arr[middle] == value) {return middle;} else if (arr[middle] > value) {return recursionBinarySearch(value, arr, low, middle - 1);} else {return recursionBinarySearch(value, arr, middle + 1, high);}}/*** 求解一個數的平方根，精確到小數六位* * @param n n* @return*/public static float square(float n) {if (n == 0 || n == 1) {return 1;}float low = 0, high = n;float middle = low + (high - low) / 2;while (Math.abs(middle * middle - n) > 0.000001) {if (middle * middle > n) {high = middle;} else if (middle * middle < n) {low = middle;} else {return middle;}middle = low + (high - low) / 2;}return middle;}/*** 利用二分查找返回數組中第一個出現value的位置,注意邊界條件middle==0* * @param arr arr* @param value value* @return*/public static int firstEqual(int[] arr, int value) {int low = 0, high = arr.length - 1, middle = low + ((high - low) >> 1);while (low <= high) {if (arr[middle] > value) {high = middle - 1;} else if (arr[middle] < value) {low = middle + 1;} else {if ((middle == 0) || (arr[middle - 1] < value)) {return middle;} else {high = middle - 1;}}middle = low + ((high - low) >> 1);}return -1;}/*** 利用二分查找返回數組中最后一個出現value的位置* * @param arr arr* @param value value* @return*/public static int lastEqual(int[] arr, int value) {int low = 0, high = arr.length - 1, middle = low + ((high - low) >> 1);while (low < high) {if (arr[middle] > value) {high = middle - 1;} else if (arr[middle] < value) {low = middle + 1;} else {if ((middle == arr.length - 1) || (arr[middle + 1] > value)) {return middle;} else {low = middle + 1;}}middle = low + ((high - low) >> 1);}return -1;}/*** 利用二分查找返回數組中第一個大于value的位置* * @param arr arr* @param value value* @return*/public static int firstGreat(int[] arr, int value) {int low = 0, high = arr.length - 1, middle = low + ((high - low) >> 1);while (low <= high) {if (arr[middle] > value && arr[middle - 1] <= value) {return middle;} else if (arr[middle] <= value) {low = middle + 1;} else {high = middle - 1;}middle = low + ((high - low) >> 1);}return -1;}/*** 利用二分查找返回數組中最后一個小于value的位置* * @param arr arr* @param value value* @return*/public static int lastLess(int[] arr, int value) {int low = 0, high = arr.length - 1, middle = low + ((high - low) >> 1);while (low <= high) {if (arr[middle] < value && arr[middle + 1] >= value) {return middle;} else if (arr[middle] >= value) {high = middle - 1;} else {low = middle + 1;}middle = low + ((high - low) >> 1);}return -1;}/*** 循環數組中使用二分查找獲取value所在位置* * @param arr arr* @param value value* @return*/public static int loopBinarySearch(int[] arr, int value) {if(arr.length < 1) {return -1;}if (arr.length == 1) {if (arr[0] == value) {return 0;} else {return -1;}}int low = 0, high = arr.length, middle = 0;// 首先獲取首末位置for (int i = 0; i < arr.length - 1; i++) {if (arr[i] > arr[i + 1]) {high = i;low = i + 1;}}if (arr[arr.length - 1] > arr[0]) {low = 0;high = arr.length - 1;}// 經過和arr[0]判斷后篩選出可能包含value的子數組if (arr[0] == value) {return 0;} else if (arr[0] < value) {low = 1;} else if (arr[0] > value) {high = arr.length - 1;}// 使用簡單二分查找獲取value位置while (low <= high) {middle = low + ((high - low) >> 1);if (arr[middle] > value) {high = middle - 1;} else if (arr[middle] < value) {low = middle + 1;} else {return middle;}}return -1;}public static void main(String[] args) {int[] arr = { 2, 1, 4, 6, 7, 3, 0, 9, 8, 5 };Arrays.sort(arr); // System.out.println(binarySearch(5, arr)); // System.out.println(recursionBinarySearch(5, arr, 0, arr.length - 1));System.out.println(square(5f));int[] arr1 = { 0, 1, 2, 3, 4, 4, 5, 5, 5, 8, 9 };System.out.println(firstEqual(arr1, 5));System.out.println(lastEqual(arr1, 5));System.out.println(firstGreat(arr1, 5));System.out.println(lastLess(arr1, 5));int[] arr2 = { 7, 8, 9, 0, 1, 2, 3, 4, 5, 6 };System.out.println(loopBinarySearch(arr2, 8));} }復制代碼

總結

以上是生活随笔為你收集整理的关于二分查找及变体的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。