String数组的二分排序
public class Bsearch {
? /*
?? String[] str = new String[]{"abai","aven","cai","creport","czz"};
?? 数组长度为1000以上，已知"rose"为数组中其中一个字符串，排列在未知位置，请用最快速度查找该字符串所在的索引
? */
?
?public static void main(String[] args) {
??String[] str = new String[] {"sdaf","fads","dsaf","sdfdsa","hdfh","rose","ghdfgh"};?
??// 这里定义一个字符串 可以很灵活的查找 任字符串
??String str1="rose";
??// 先进行排序
??stringBubble(str);
??
??// 排序后输出
??printStr(str);
??
???? // 找到其索引
??int index=seach(str,str1);?
??
??System.out.println(index);
??
?}
?private static void printStr(String[] strs) {
?? for(String str:strs){
??? System.out.print(str+" ");
???
?? }
?? System.out.println();
?? System.out.print("找该字符串所在的索引为: ");
??
?}
?private static int seach(String[] strs, String str1) {
?????????
??int? start=0;
??int? end=strs.length-1;?
??int? mid=0;
??// 防止进入死循环
??while(mid<=end){?
???if(mid==end && !strs[mid].equals(str1)){
???????? return 0;
???}
???// 往前折半查找
???if(strs[mid].compareTo(str1)>0){
???? end = mid;???
???? if((start+end)%2==0){
????? mid=(start+end)/2;
???? }
???? else{?
????? mid=(start+end)/2 +1;
???? }
???? continue;
???}
???// 往后折半查找
???else if(strs[mid].compareTo(str1)<0){
????? ? start=mid;
????? ? if((start+end)%2==0){
????? ?? mid=(start+end)/2;
????? ? }else{
????? ?? mid=(start+end)/2+1;
????? ? }
????? ? continue;
????? }
???// 找到了
????? else if(strs[mid].compareTo(str1)==0){
????? ?return mid;
????? ?
????? }
???
??}
??return 0;
??
??
?}
?
?public static String[] stringBubble(String[] arr) {
??for (int i = 0; i < arr.length - 1; i++) {
???for (int j = 0; j < arr.length - i - 1; j++) {
????if (arr[j].compareTo(arr[j + 1]) > 0) {
?????swap(arr, j, j + 1);
????}
???}
??}
??return arr;
?}
?public static void swap(String[] arr, int a, int b) {
??String temp = arr[a];
??arr[a] = arr[b];
??arr[b] = temp;
?}
}
