二分查找：

二分查找也叫折半查找，也就是把n個元素拆成一半一半查找。二分查找有兩個要求第一個是要是有序的數列，第二個是必須存儲在連續的存儲結構中。假如數列是無序的，可以先使用排序算法排序。

實現：

分析：

1.定義個中間值middle，middle=（left+rigth)/2。把他做為要查找值的下標。
2.查找值key和middle比較：
key>middle說明查找值在middle的右邊，改變left的值，left=middle+1.從而也改變了中間值。
key<middle查找值在middle的左邊，改變rigth的值，rigth=middle-1.
key=middle時，輸出下標middle。
注意我們何時結束查找呢
1.找到了查找值，結束。
2.left>rigth時結束（不是在循環中寫left>rigth，這樣會沒有輸出結果）

實現：

不遞歸的：

package day07;/*
Author:
date:
problem: 二分查找：（不遞歸）
    /*
    1.不遞歸的可以用while循環。middle=left+rigth/2
    2.left=0,ringth=array0.length用if判斷是不是大于如果大于就把交換
     */


import java.util.Scanner;

public class binayarray {
    public static void main(String[] args) {
        int[] array0 = {1, 4, 6, 9, 10, 12, 14, 16, 18};
            int middle=0;//定義一個中間值，查找的下標
            int left = 0;
            int i=0;
            int rigth = array0.length - 1;
            System.out.println("請輸入要查找的值");
            Scanner sca = new Scanner(System.in);
            int key = sca.nextInt();
            while (left<=rigth) {//當left>rigth時結束，說明已經循環完數組了
                middle = (left + rigth) / 2;
                if (key > array0[middle]) {
                    left = middle + 1;
                } else if (key < array0[middle]) {
                    rigth = middle - 1;
                } if (key == array0[middle]) {
                    i=middle;
                }
            }System.out.println(i);
        }
    }

優化思考：

1.數列有序，有重復值。
數列是升序排序，但數列中重復的值如{1，2，3，4，2，2，2，2，}我們查找2這個數時，只會輸出第一重復值的下標
找到這個數的右邊界，rigth–.

package day07;/*
Author:
date:
problem: 二分查找：（不遞歸）
    /*
    1.不遞歸的可以用while循環。middle=left+rigth/2
    2.left=0,ringth=array0.length用if判斷是不是大于如果大于就把交換
     */


import java.util.Scanner;
//尋找邊界值
public class binayarray {
    public static void main(String[] args) {
        int[] array0 = {1, 4, 6, 9, 9, 9, 14, 16, 18};
            int middle=0;//定義一個中間值，查找的下標
            int left = 0;
            int i=0;
            int rigth = array0.length - 1;
            System.out.println("請輸入要查找的值");
            Scanner sca = new Scanner(System.in);
            int key = sca.nextInt();
            while (left<=rigth) {//當left>rigth時結束，說明已經循環完數組了
                middle = (left + rigth) / 2;
                if (key > array0[middle]) {
                    left = middle + 1;
                } else if (key < array0[middle]) {
                    rigth = middle - 1;
                } if (key == array0[middle]) {//有重復的數，可以收縮右邊界，找到最邊上的
                    rigth--;

                    i=middle;
                }
            }System.out.println(i);
        }
    }