# 二分搜尋法（搜尋原則的代表）

## 解法

[3 24 57 57 67 68 83 90 92 95]

3 24 57 57 67 [68 83 90 92 95]

3 24 57 57 67 68 83 90 [92 95]

## 實作：CJavaPythonScalaRuby

• C
``#include <stdio.h> #include <stdlib.h> #include <time.h> #define MAX 10 #define SWAP(x,y) {int t; t = x; x = y; y = t;} void quickSort(int[], int, int); int binarySearch(int[], int); int main(void) {     srand(time(NULL));         int number[MAX] = {0};     int i;    for(i = 0; i < MAX; i++) {         number[i] = rand() % 100;     }     quickSort(number, 0, MAX-1);     printf("數列：");     for(i = 0; i < MAX; i++)         printf("%d ", number[i]);     int find;    printf("\n輸入尋找對象：");     scanf("%d", &find);     if((i = binarySearch(number, find)) >= 0)         printf("找到數字於索引 %d ", i);     else         printf("\n找不到指定數");         printf("\n");     return 0; } int binarySearch(int number[], int find) {     int low = 0;     int upper = MAX - 1;     while(low <= upper) {         int mid = (low+upper) / 2;         if(number[mid] < find)             low = mid+1;         else if(number[mid] > find)             upper = mid - 1;         else             return mid;     }     return -1; } void quickSort(int number[], int left, int right) {     if(left < right) {         int s = number[(left+right)/2];         int i = left - 1;         int j = right + 1;         while(1) {             while(number[++i] < s) ;  // 向右找             while(number[--j] > s) ;  // 向左找             if(i >= j)                 break;             SWAP(number[i], number[j]);         }         quickSort(number, left, i-1);   // 對左邊進行遞迴         quickSort(number, j+1, right);  // 對右邊進行遞迴     } } ``

• Java
``public class Search {    public static int binary(int[] number, int des) {        int low = 0;         int upper = number.length - 1;         while(low <= upper) {             int mid = (low+upper) / 2;             if(number[mid] < des)                 low = mid+1;             else if(number[mid] > des)                 upper = mid - 1;             else                 return mid;         }         return -1;     }        public static void main(String[] args) {        int[] number = {1, 2, 3, 4, 6, 7, 8};        int find = Search.binary(number, 2);        System.out.println(find >= 0 ? "找到數值於索引" + find : "找不到數值");     }} ``

• Python
``def search(number, des):    low = 0    upper = len(number) - 1    while low <= upper:        mid = (low + upper) // 2        if number[mid] < des:            low = mid + 1        elif number[mid] > des:            upper = mid - 1        else:            return mid    return -1number = [1, 4, 2, 6, 7, 3, 9, 8]number.sort()find = search(number, 2)print("找到數值於索引 " + str(find) if find >= 0 else "找不到數值")  ``

• Scala
``object Search {    def binary(number: Array[Int], des: Int) = {        var low = 0        var upper = number.length - 1        var result = -1        var isContinue = true        while(isContinue && low <= upper) {            val mid = (low + upper) / 2            if(number(mid) < des) {                low = mid + 1            }            else if(number(mid) > des) {                upper = mid - 1            }            else {                result = mid                isContinue = false            }        }        result    }}val number = Array(1, 2, 3, 4, 6, 7, 8)val find = Search.binary(number, 3)println(if(find >= 0) "找到數值於索引 " + find else "找不到數值")``

• Ruby
``# encoding: Big5def search(number, des)    low = 0    upper = number.length - 1    while low <= upper        mid = (low + upper) / 2        if number[mid] < des            low = mid + 1        elsif number[mid] > des            upper = mid - 1        else            return mid        end    end    -1endnumber = [1, 4, 2, 6, 7, 3, 9, 8]number.sort!find = search(number, 2)print find >= 0 ? "找到數值於索引 " + find.to_s : "找不到數值", "\n"``