二分法在有序数组中查找某一值

public class Find {

  public static int find(int[] array, int aim) {
    int left=0;
    int right=array.length-1;
    while(left<=right){
      int middle=(left+right)/2;
      int middlevalue=array[middle];
      if(middlevalue==aim){
        return middle;
      }else if(middlevalue<aim){
        right=middle-1;
      }else if(middlevalue>aim){
        left=middle+1;
      }
    }
    return -1;
  }
  public static void main(String[] args) {
    int[] array = {100, 90, 80, 75, 22, 3, 2};
    int result1 = find(array, 22);
    if (result1 == -1) {
      System.out.println("22 不存在数组中");
    } else {
      System.out.println("22 存在数组中,索引值是 " + result1);
    }

    int result2 = find(array, 50);
    if (result2 == -1) {
      System.out.println("50 不存在数组中");
    } else {
      System.out.println("50 存在数组中,索引值是 " + result2);
    }
  }
}

分析:

主函数为输出(不论)

在子函数中,设定left,right作为数组两端值(right为长度减一)

当left>right时候跳出循环

设定一个middle为right和left的中值,提取middle代表的数组中的数

如果提取数为目标值则输出

如果提取数大于目标值(在单调增数组中)则目标值在提取数前,则right=middle-1;

反之 left=middle+1;

以此寻找值

注:此方法也可用于查找string

利用 string1.compareTo(string2)可以判断string的大小关系(具体是从string第一个字母开始依次按ABCD排序)如果返回值是负数则string1在string2前,反之在后。