首页 > 代码库 > 爪哇国新游记之二十七----数组的二分查找
爪哇国新游记之二十七----数组的二分查找
代码:
import java.util.ArrayList;import java.util.List;public class Bit { int max; int min; int[] arr; public Bit(int[] arrInput) { // 找出极值 for (int i = 0; i < arrInput.length; i++) { if (max < arrInput[i]) { max = arrInput[i]; } if (min > arrInput[i]) { min = arrInput[i]; } } // 新建数组 arr = new int[max - min + 1]; // 数组插值 for (int i : arrInput) { int index = i - min; arr[index]++; } } public boolean hasDuplicateItem() { for (int i = 0; i < arr.length; i++) { int value =http://www.mamicode.com/ arr[i]; if (value > 1) { return true; } } return false; } public List<Integer> getSortedList() { List<Integer> ls = new ArrayList<Integer>(); for (int i = 0; i < arr.length; i++) { int value =http://www.mamicode.com/ arr[i]; if (value != 0) { for (int j = 0; j < value; j++) { ls.add(min + i); } } } return ls; } public List<Integer> getUniqueSortedList() { List<Integer> ls = new ArrayList<Integer>(); for (int i = 0; i < arr.length; i++) { int value =http://www.mamicode.com/ arr[i]; if (value != 0) { ls.add(min + i); } } return ls; } public int[] getUniqueSortedArray(){ List<Integer> ls=getUniqueSortedList(); int[] arr=new int[ls.size()]; for(int i=0;i<arr.length;i++){ arr[i]=ls.get(i); } return arr; } /** * 二分查找 * * @param sortedArray * 已排序的欲查找的数组 * @param seachValue * 查找的值 * @return 找到的元素下标,若找不到则返回-1 */ public static int binSearch(int[] sortedArray, int seachValue) { // 左边界 int leftBound = 0; // 右边界 int rightBound = sortedArray.length - 1; // 当前下标位置 int curr; while (true) { // 定位在左边界和右边界中间 curr = (leftBound + rightBound) / 2; if (sortedArray[curr] == seachValue) { // 找到值 return curr; } else if (leftBound > rightBound) { // 左边界大于右边界,已经找不到值 return -1; } else { if (sortedArray[curr] < seachValue) { // 当当前下标对应的值小于查找的值时,缩短左边界 leftBound = curr + 1; } else { // 当当前下标对应的值大于查找的值时,缩短右边界 rightBound = curr - 1; } } } } public static void main(String[] args) { int[] arr = { -2, -1, 3, 5, 7, 9, 30, 4, -2, 5, 8, 3 }; Bit b = new Bit(arr); System.out.println("排序后数组"); int[] arr2=b.getUniqueSortedArray(); for(int i=0;i<arr2.length;i++){ System.out.println(i+":"+arr2[i]); } int[] arr3={2,5,7,-2,90}; for(int i=0;i<arr3.length;i++){ int index=Bit.binSearch(arr2, arr3[i]); if(index!=-1){ System.out.println(arr3[i]+"排在数组arr2的第"+index+"个"); }else{ System.out.println(arr3[i]+"不在数组arr2中"); } } }}
输出:
排序后数组0:-21:-12:33:44:55:76:87:98:302不在数组arr2中5排在数组arr2的第4个7排在数组arr2的第5个-2排在数组arr2的第0个90不在数组arr2中
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。