二分查找：

二分查找也叫折半查找，也就是把n個(gè)元素拆成一半一半查找。二分查找有兩個(gè)要求第一個(gè)是要是有序的數(shù)列，第二個(gè)是必須存儲(chǔ)在連續(xù)的存儲(chǔ)結(jié)構(gòu)中。假如數(shù)列是無序的，可以先使用排序算法排序。

實(shí)現(xiàn)：

分析：

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

實(shí)現(xiàn)：

不遞歸的：

package day07;/*
Author:
date:
problem: 二分查找：（不遞歸）
    /*
    1.不遞歸的可以用while循環(huán)。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;//定義一個(gè)中間值，查找的下標(biāo)
            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) {//當(dāng)left>rigth時(shí)結(jié)束，說明已經(jīng)循環(huán)完數(shù)組了
                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);
        }
    }

優(yōu)化思考：

1.數(shù)列有序，有重復(fù)值。
數(shù)列是升序排序，但數(shù)列中重復(fù)的值如{1，2，3，4，2，2，2，2，}我們查找2這個(gè)數(shù)時(shí)，只會(huì)輸出第一重復(fù)值的下標(biāo)
找到這個(gè)數(shù)的右邊界，rigth–.

package day07;/*
Author:
date:
problem: 二分查找：（不遞歸）
    /*
    1.不遞歸的可以用while循環(huán)。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;//定義一個(gè)中間值，查找的下標(biāo)
            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) {//當(dāng)left>rigth時(shí)結(jié)束，說明已經(jīng)循環(huán)完數(shù)組了
                middle = (left + rigth) / 2;
                if (key > array0[middle]) {
                    left = middle + 1;
                } else if (key < array0[middle]) {
                    rigth = middle - 1;
                } if (key == array0[middle]) {//有重復(fù)的數(shù)，可以收縮右邊界，找到最邊上的
                    rigth--;

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