本文主要是介绍二分法变种,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
package compublic class Test {public static void main(String[] args) {int[] nums = {4,7,7,9,12,13};int index = searchLastSmaller(nums,1);System.out.println(index);}/** 第一个与key相等的元素*/public static int searchFirstEqual(int[] arr, int key){int left = 0, right = arr.length-1;while(left<=right){int mid = (left+right)/2;if(arr[mid]>=key)right=mid-1;else if(arr[mid]<key) left = mid+1;}if(left<arr.length&&arr[left]==key) return left;return -1;}/** 找出最后一个与key相等的元素*/public static int searchLastEqual(int[] arr, int key){int left = 0, right = arr.length-1;while(left<=right) {int mid = (left+right)/2;if(arr[mid] > key) right = mid - 1;else if(arr[mid] <= key) left = mid + 1; }if( right>=0 && arr[right] == key) return right;return -1;}/** 找出第一个大于等于key的元素* */public static int searchFirstEqualOrLarger(int arr[],int key){int left=0, right=arr.length-1;while(left<=right) {int mid = (left+right)/2;if(arr[mid] >= key) right = mid-1;else if (arr[mid] < key) left = mid+1;}if(left>=arr.length)return -1;return left;}/** 查找第一个大于key的元素*/public static int searchFirstLarger(int[] arr, int key){int left=0, right=arr.length-1;while(left<=right) {int mid = (left+right)/2;if(arr[mid] > key) right = mid-1;else if (arr[mid] <= key) left = mid+1;}if(left>=arr.length)return -1;return left;}/** 查找最后一个小于或等于Key的元素*/public static int searchLastEqualOrSmaller(int[] arr, int key){int left=0, right=arr.length-1;while(left<=right) {int m = (left+right)/2;if(arr[m] > key) right = m-1;else if (arr[m] <= key) left = m+1;}//若right=-1,表明不存在return right;}/** 查找最后一个小于key的元素*/public static int searchLastSmaller(int[] arr, int key){int left=0, right=arr.length-1;while(left<=right) {int mid = (left+right)/2;if(arr[mid] >= key) right = mid-1;else if (arr[mid] < key) left = mid+1;}//若right=-1,表明不存在return right;}}
这篇关于二分法变种的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!