package dichotomy;
import java.util.Arrays;
import java.util.Scanner;
import static java.lang.System.out;
public class Erchange {
 
 private static Scanner in;
 public int find(int a[],int b) //a為所要查找的數(shù)
 {
 int mid,low=0,high;
 high=a.length-1;
 while(low<=high)
 {
  mid=low+(high-low)/2;
  if(b<a[mid])
  {
  high=mid-1;
  }
  else if(b>a[mid])
  {
  low=mid+1;
  }
  else
 {
  return mid+1;
  } 
 }
 return 0;
 }
 public static void main(String[] args) {
  int a[];
  int t;
  int sum=0;
  Erchange p=new Erchange();
  int q2 = 0;
  in = new Scanner(System.in);
  out.println("請(qǐng)輸入數(shù)組長(zhǎng)度");
 q2= in.nextInt();
  a=new int [q2];
  out.println("請(qǐng)輸入數(shù)組元素");
  for(int i=0;i<a.length;i++)
  {
  a[i]=in.nextInt();
  }
  out.println("排序后數(shù)組為");
  Arrays.sort(a);
  for (int i = 0; i < a.length; i++) {
  out.print(a[i]+" ");
  }
  out.println();
  out.println("請(qǐng)輸入所要查找的數(shù)若未查找到該數(shù)則輸出-1");
  q2=in.nextInt();
  for(int i=0;i<a.length;i++)
  {
  if(q2==a[i])
  {
   t=1;
  }
  else
  {
   t=0;
  }
  sum=sum+t;
 }
 if(sum==0)
 {
  out.println("-1");
 }
 else
 {
 out.println("所輸入的數(shù)在第"+p.find(a,q2)+"位");
 }
}

public class BinarySearch {
//進(jìn)行二分法查找的前提是數(shù)組已經(jīng)有序！
	public static int rank(int key,int nums[])
	{
		//查找范圍的上下界
		int low=0;
		int high=nums.length-1;
		//未查找到的返回值
		int notFind=-1;
		while(low<=high)
		{
			//二分中點(diǎn)=數(shù)組左邊界+(右邊界-左邊界)/2
			//整數(shù)類型默認(rèn)取下整
			int mid=low+(high-low)/2;
			//中間值是如果大于key
			if(nums[mid]>key)
			{
				//證明key在[low,mid-1]這個(gè)區(qū)間
				//因?yàn)閚um[mid]已經(jīng)判斷過(guò)了所以下界要減一
				high=mid-1;
			}else if(nums[mid]<key)
			{
				//證明key在[mid+1,high]這個(gè)區(qū)間
				//同樣判斷過(guò)mid對(duì)應(yīng)的值要從mid+1往后判斷
				low=mid+1;
			}
			else
			{
				//查找成功
				return mid;
			}
		}
		//未成功
		return notFind;
	}
	public static void main(String[] args) {
		System.out.println("請(qǐng)輸入數(shù)據(jù)數(shù)量：");
		Scanner scanner=new Scanner(System.in);
		int amount=scanner.nextInt();
		int num;
		int nums[]=new int[amount];
		int i=0;
		while(i<amount)
		{
			nums[i]=scanner.nextInt();
			i++;
		}
		Arrays.sort(nums);
		System.out.println("請(qǐng)輸入想要查找的值");
		int key=scanner.nextInt();
		int answer=rank(key,nums);
		if(answer!=-1)
		{
			System.out.println("所查找的數(shù)據(jù)存在："+nums[answer]);
		}
		else
		{
			System.out.println("您所查找的數(shù)據(jù)不存在");
		}
	}
 
}

package com.roc.algorithms.search;
 
/**
 * 二分法查找
 *
 * @author roc
 */
public class BinarySearch {
 
  /**
   * @param a 升序排列的數(shù)組
   * @param k 待查找的整數(shù)
   * @return 如果查到有就返回對(duì)應(yīng)角標(biāo)，沒(méi)有就返回-1
   */
  public static int search(int[] a, int k) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
      int m = (lo + hi) >> 1;
      if (a[m] < k) {
        lo = m + 1;
      } else if (a[m] > k) {
        hi = m - 1;
      } else {
        return m;
      }
    }
    return -1;
  }
}

int[] a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
System.out.println(BinarySearch.search(a, 6));