ProgrammingTasks

Бинарный поиск

Этот вид поиска применим только к отсортированным массивам. Его идея заключается в том, что сначала выбирается элемент в середине массива. Поскольку массив отсортирован, то если искомый элемент больше выбранного, то поиск далее продолжается только в правой части массива. Соответственно, если искомый элемент меньше, просматривается только левая половина массива. Ну если средний элемент является искомым, то поиск завершается сразу же.

Таким образом, этот метод выполняется быстрее остальных алгоритмов поиска. Его асимптотическая сложность — O(log N).

Далее приводится реализация алгоритма на разных языках программирования.

#include <stdio.h>

int binary_search(const int ar[], int length, int item)
{

	int middle, left, right;

	left = 0;
	right = length - 1;

	do {
		middle = (left+right) / 2;

		if (item > ar[middle])
			left = middle + 1;
		else
			right = middle - 1;
	} while(ar[middle]!=item && left<=right);

	if (ar[middle] == item)
		return middle;

	return -1;
}

int main(void)
{
	const int arr[] = {1,2,3,4,5};
	int length = sizeof(arr) / sizeof(*arr);
	int item = 3;
	int found = binary_search(arr, length, item);

	printf("item = %d, index = %d\n", item, found);

	return 0;
}
 internal class Program
 {
     static int BinarySearch(T[] arr, T item) where T:IComparable
     {
         Array.Sort(arr);
         int length = arr.Length;
         int middle = 0;
         int left = 0;
         int right= length - 1;

         do {
             middle = (left+right)/2;
             if (item.CompareTo(arr[middle])==1)
             {
                 left = middle + 1;
             }
             else
             {
                 right = middle - 1;
             }
         } while(arr[middle].CompareTo(item)!=0 && left <= right);   

         if (arr[middle].CompareTo(item)==0)
         {
             return middle;
         }

         return -1;
     }

     static void Main(string[] args)
     {
         int[] arr = { 10, 2, 5, 1, 15, 12, 20 };
        
         int item = 1;
        
         int index=BinarySearch(arr, item);
         
         Console.WriteLine($"Array: {string.Join(" ", arr)}\nitem = {item}, index = {index}");

         Console.ReadKey();
     }
 }

<?php
function BinarySearch(array $arr, int $item): int 
{
    sort($arr);
    
    $length=count($arr);

    $left=0;
    $right=$length-1;

    do {
       $middle=floor(($left+$right)/2);
       if ($item>$arr[$middle]) {
          $left=$middle+1;
       } 
       else {
          $right=$middle-1;
       }
    } while($arr[$middle]!=$item && $left<=$right);

    if ($arr[$middle]==$item) {
        return $middle;
    }

    return -1;
}
function BinarySearch(arr, item) {
    if (Array.isArray(arr)) {

       arr.sort((a, b)=>a-b);

       const len=arr.length;
       let left=0;
       let right=len-1;
       let middle=0;

       do {
          middle=Math.floor((left+right)/2);
          if (item>arr[middle]) {
             left=middle+1;
          }
          else {
             right=middle-1;
          }
       } while(arr[middle]!=item && left<=right);

       if (arr[middle]===item) {
          return middle;
       }

       return -1;
     }
     else {
         throw new Error("First argument must be of type Array");
     }
}