Java 实现折半查找

1 packagesearch;
2 import java.util.*;
3 /*折半查找要求线性表是有序的，假设递增
4 * 基本思路：R[low...high]是当前的查找区间，首先确定中间位置mid=(low+high)/2,将待查关键字k与R[mid]比较，
5 * 若相等查找成功，若R[mid]>k,则新的查找区间为R[low...mid-1],若R[mid]<k,则新的查找区间为R[mid+1...high],
6 * 相同的方式处理新的区间，直到区间的长度小于1，查找结束*/
7 public classzhebansearch {
8 
9     public static voidmain(String[] args){
10         Scanner cin = newScanner(System.in);
11         String[] str=new String[2];
12         for(int i=0;i<2;i++){
13             str[i] =cin.nextLine();
14 }        
15         String[] st = str[0].split(" ");
16         int[] c = new int[st.length];
17         for(int i=0;i<c.length;i++){
18             c[i]=Integer.parseInt(st[i]);
19 }
20         int key = Integer.parseInt(str[1]);
21         int result =search(c,key);
22         System.out.print(result+1);//找到返回相应索引值（从1开始），没找到返回1
23 }
24     public static int search(int[] R,intk){
25         int length =R.length;
26         int mid,low=0,high=length;
27         while(low<=high){
28             mid = (low+high)/2;
29             if(R[mid]==k){
30                 returnmid;
31             }else if(R[mid]>k){
32                 high=mid-1;
33             }else{
34                 low=mid+1;
35 }
36 }
37         return -1;
38 }
39 }