二進位（二分查找）搜索

二進位搜索是一種在排序列表上有效工作的搜索技術。 因此，要使用二進位搜索技術來搜索某個列表中的元素，需要確保對列表是一個已排好順序。

二進位搜索遵循分而治之的方法，其中，列表被分成兩半，並且專案與列表的中間元素進行比較。 如果找到匹配，則返回中間元素的位置，否則根據匹配產生的結果搜索到兩半中的任何一個。

二進位搜索演算法如下。

BINARY_SEARCH(A, lower_bound, upper_bound, VAL)
第1步: [INITIALIZE] SET BEG = lower_bound
    END = upper_bound, POS = - 1
第2步: Repeat Steps 3 and 4 while BEG <=END
第3步: SET MID = (BEG + END)/2
第4步: IF A[MID] = VAL
    SET POS = MID
    PRINT POS
轉到第6步

    ELSE IF A[MID] > VAL
    SET END = MID - 1
    ELSE
    SET BEG = MID + 1
    [END OF IF]
    [END OF LOOP]
第5步: IF POS = -1
    PRINT "VALUE IS NOT PRESENT IN THE ARRAY"
    [END OF IF]
第6步: EXIT

複雜度

示例

考慮有一個數組arr = {1,5,7,8,13,19,20,23,29}，要在數組中查找專案：23的位置。

第1步：

BEG = 0
END = 8ron
MID = 4
a[mid] = a[4] = 13 < 23, 那麼

第2步：

Beg = mid +1 = 5
End = 8
mid = 13/2 = 6
a[mid] = a[6] = 20 < 23, 那麼;

第3步：

beg = mid + 1 = 7
End = 8
mid = 15/2 = 7
a[mid] = a[7]
 a[7] = 23 = item;
那麼, 設置 location = mid;
專案的位置為： 7

演算法可參考以下圖解 -

使用遞歸的二進位搜索程式

使用C語言實現 -

#include<stdio.h>
int binarySearch(int[], int, int, int);
void main ()
{
    int arr[10] = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};
    int item, location=-1;
    printf("Enter the item which you want to search ");
    scanf("%d",&item);
    location = binarySearch(arr, 0, 9, item);
    if(location != -1)
    {
        printf("Item found at location %d",location);
    }
    else
    {
        printf("Item not found");
    }
}
int binarySearch(int a[], int beg, int end, int item)
{
    int mid;
    if(end >= beg)
    {
        mid = (beg + end)/2;
        if(a[mid] == item)
        {
            return mid+1;
        }
        else if(a[mid] < item)
        {
            return binarySearch(a,mid+1,end,item);
        }
        else
        {
            return binarySearch(a,beg,mid-1,item);
        }

    }
    return -1;
}

執行上面示例代碼，得到以下結果：

Enter the item which you want to search
19
Item found at location 2

Java語言實現二進位查找 -

import java.util.*;
public class BinarySearch {
public static void main(String[] args) {
    int[] arr = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};
    int item, location = -1;
    System.out.println("Enter the item which you want to search");
    Scanner sc = new Scanner(System.in);
    item = sc.nextInt();
    location = binarySearch(arr,0,9,item);
    if(location != -1)
    System.out.println("the location of the item is "+location);
    else
        System.out.println("Item not found");
    }
public static int binarySearch(int[] a, int beg, int end, int item)
{
    int mid;
    if(end >= beg)
    {
        mid = (beg + end)/2;
        if(a[mid] == item)
        {
            return mid+1;
        }
        else if(a[mid] < item)
        {
            return binarySearch(a,mid+1,end,item);
        }
        else
        {
            return binarySearch(a,beg,mid-1,item);
        }

    }
    return -1;
 }
}

執行上面示例代碼，得到以下結果 -

Enter the item which you want to search
45
the location of the item is 5

C#語言實現示例代碼 -

using System;

public class LinearSearch
{
    public static void Main()
    {
    int[] arr = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};
    int location=-1;
    Console.WriteLine("Enter the item which you want to search ");
    int item = Convert.ToInt32(Console.ReadLine());
    location = binarySearch(arr, 0, 9, item);
    if(location != -1)
    {
        Console.WriteLine("Item found at location "+ location);
    }
    else
    {
        Console.WriteLine("Item not found");
    }
}
public static int binarySearch(int[] a, int beg, int end, int item)
{
    int mid;
    if(end >= beg)
    {
        mid = (beg + end)/2;
        if(a[mid] == item)
        {
            return mid+1;
        }
        else if(a[mid] < item)
        {
            return binarySearch(a,mid+1,end,item);
        }
        else
        {
            return binarySearch(a,beg,mid-1,item);
        }

    }
    return -1;

    }
}

執行上面示例代碼，得到以下結果 -

Enter the item which you want to search
20
Item found at location 3

Python語言實現代碼 -

def binarySearch(arr,beg,end,item):
    if end >= beg:
        mid = int((beg+end)/2)
        if arr[mid] == item :
            return mid+1
        elif arr[mid] < item :
            return binarySearch(arr,mid+1,end,item)
        else:
            return binarySearch(arr,beg,mid-1,item)
    return -1


arr=[16, 19, 20, 23, 45, 56, 78, 90, 96, 100];
item = int(input("Enter the item which you want to search ?"))
location = -1;
location = binarySearch(arr,0,9,item);
if location != -1:
    print("Item found at location %d" %(location))
else:
    print("Item not found")

執行上面示例代碼，得到以下結果 -

Enter the item which you want to search ?
96
Item found at location 9

Enter the item which you want to search ?
101
Item not found

使用迭代的二進位搜索函數實現 -

int binarySearch(int a[], int beg, int end, int item)
{
    int mid;
    while(end >= beg)
    {
        mid = (beg + end)/2;
        if(a[mid] == item)
        {
            return mid+1;
        }
        else if(a[mid] < item)
        {
            beg = mid + 1;
        }
        else
        {
            end = mid - 1;
        }

    }
    return -1;
}