java二分查找算法字符串数组_Java 算法——二分查找数组集合关键元素

packagecom.sinosoft;import java.util.*;importjava.util.stream.Stream;/***@authorCreated by xushuyi

* @Description

* @date 2019/1/17 10:41*/

public classArrayTest {public static voidmain(String[] args) {/*** 1. 遍历一个数组 获取最大值

* 2. 采用二分法*/getArrayMaxVal();

}/*** 1. 遍历一个数组 获取最大值

* 2. 采用二分法，前提必须是连续(升序/降序)数组，前提没有重复元素*/

private static voidgetArrayMaxVal() {//定义一个list数组集合

List list = new ArrayList<>(100);

addListVal(list);

System.out.println("集合：" +list);//默认是 按照升序排列//Collections.sort(list);//数组反转//Collections.reverse(list);//通过比较策略 来按照升序/降序排列

Collections.sort(list, new Comparator() {

@Overridepublic intcompare(Integer o1, Integer o2) {return o1 - o2; //升序 如果 o1 小于 o2 返回 -1， 相等返回 0 ，o1 大于 o2 返回 1//return o2 - o1;//降序 如果 o1 小于 o2 返回 1， 相等返回 0 ，o1 大于 o2 返回 -1

}

});

System.out.println("排序后：" +list);//集合开始位置

int startIndex = 0;//集合结束位置

int endIndex = list.size() - 1;//定义查找集合中的元素

int key = 2;//采用递归的方式进行查找(推荐)

int val =searchList(list, startIndex, endIndex, key);

System.out.println("递归查找结果：" +val);//采用非递归的方式进行查找

val =searchList1(list, startIndex, endIndex, key);

System.out.println("非递归查找结果：" +val);

}/*** 采用二分法来查找集合中的关键元素

*

*@paramlist 有序集合

*@paramstartIndex 集合开始下标

*@paramendIndex 集合结束下标

*@paramkey 查找关键元素

*@returnint*/

private static intsearchList1(

Listlist,intstartIndex,intendIndex,intkey) {//满足 开始下标 不大于 结束下标才行

while (startIndex <=endIndex) {int middleIndex = (endIndex - startIndex) / 2 +startIndex;if (key ==list.get(middleIndex))returnmiddleIndex;if (key >list.get(middleIndex))//说明在[middle, end]之间，需要重置 开始下标为 中间位置+1，抛弃[start,middle]集合查找

startIndex = middleIndex + 1;else if (key

endIndex = middleIndex - 1;else

//集合中没有找到指定的元素

return -1;

}return -1;

}/*** 采用二分法查找集合中的关键元素

* 采用递归的方式

*

*@paramlist 有序集合

*@paramstartIndex 开始下标

*@paramendIndex 结束下标

*@paramkey 查找关键元素*/

private static intsearchList(

Listlist,intstartIndex,intendIndex,intkey) {int middleIndex = (endIndex - startIndex) / 2 +startIndex;

System.out.println("中间位置：" +middleIndex);if (key ==list.get(middleIndex)) {returnmiddleIndex;

}if (startIndex >=endIndex) {return -1;

}//说明在 [middle，end]之间

else if (key >list.get(middleIndex)) {return searchList(list, middleIndex + 1, endIndex, key);

}//说明在[start, middle]之间

else if (key

}else{return -1;

}

}/*** 对list集合进行赋值

*

*@paramlist 集合*/

private static void addListVal(Listlist) {//for (int i = 0; i < 88; i++) {//list.add(i);//}

list.add(1);

list.add(2);

list.add(3);

list.add(4);

list.add(7);

list.add(8);

list.add(9);

list.add(10);

list.add(5);

list.add(6);

}

}