Двоично търсене

В този урок ще научите как работи сортирането с двоично търсене. Също така ще намерите работещи примери за двоично търсене в C, C ++, Java и Python.

Бинарното търсене е алгоритъм за търсене за намиране на позицията на елемент в сортиран масив.

При този подход елементът винаги се търси в средата на част от масив.

Двоичното търсене може да се осъществи само в сортиран списък с елементи. Ако елементите вече не са сортирани, първо трябва да ги сортираме.

Работа с двоично търсене

Алгоритъм за двоично търсене може да бъде реализиран по два начина, които са разгледани по-долу.

  1. Итеративен метод
  2. Рекурсивен метод

Рекурсивният метод следва подхода „разделяй и владей“.

Общите стъпки за двата метода са разгледани по-долу.

  1. Масивът, в който трябва да се извърши търсенето, е: Първоначален масив
    Нека x = 4бъде елементът, който трябва да се търси.
  2. Поставете два указателя ниско и високо съответно на най-ниската и най-високата позиция. Задаване на указатели
  3. Намерете средния елемент в средата на масива, т.е. (arr(low + high)) / 2 = 6. Среден елемент
  4. Ако x == mid, тогава върнете mid.Else, сравнете елемента, който ще търсите, с m.
  5. Ако x> mid, сравнете x със средния елемент на елементите от дясната страна на средата. Това става чрез задаване на ниско на low = mid + 1.
  6. В противен случай сравнете x със средния елемент на елементите от лявата страна на средата. Това се прави, като се постави високо на high = mid - 1. Намиране на средния елемент
  7. Повторете стъпки от 3 до 6, докато ниското се срещне с високо. Среден елемент
  8. x = 4е намерен. Намерен

Алгоритъм на двоично търсене

Метод на итерация

правете, докато указателите ниско и високо се срещнат помежду си. mid = (low + high) / 2 if (x == arr (mid)) return mid else if (x> A (mid)) // x е от дясната страна low = mid + 1 else // x е включен лявата страна високо = средата - 1

Рекурсивен метод

 binarySearch (arr, x, low, high) if low> high return False else mid = (low + high) / 2 if x == arr (mid) return mid else if x <data (mid) // x is on the дясна страна връща binarySearch (arr, x, mid + 1, high) else // x е от дясната страна връща binarySearch (arr, x, low, mid - 1)

Примери за Python, Java, C / C ++ (итеративен метод)

Python Java C C ++ 
 # Binary Search in python def binarySearch(array, x, low, high): # Repeat until the pointers low and high meet each other while low <= high: mid = low + (high - low)//2 if array(mid) == x: return mid elif array(mid) < x: low = mid + 1 else: high = mid - 1 return -1 array = (3, 4, 5, 6, 7, 8, 9) x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found")
 // Binary Search in Java class BinarySearch ( int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) public static void main(String args()) ( BinarySearch ob = new BinarySearch(); int array() = ( 3, 4, 5, 6, 7, 8, 9 ); int n = array.length; int x = 4; int result = ob.binarySearch(array, x, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); ) )
 // Binary Search in C #include int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int n = sizeof(array) / sizeof(array(0)); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); return 0; )
 // Binary Search in C++ #include using namespace std; int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int x = 4; int n = sizeof(array) / sizeof(array(0)); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )

Примери за Python, Java, C / C ++ (рекурсивен метод)

Python Java C C ++ 
 # Binary Search in python def binarySearch(array, x, low, high): if high>= low: mid = low + (high - low)//2 # If found at mid, then return it if array(mid) == x: return mid # Search the left half elif array(mid)> x: return binarySearch(array, x, low, mid-1) # Search the right half else: return binarySearch(array, x, mid + 1, high) else: return -1 array = (3, 4, 5, 6, 7, 8, 9) x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found")
 // Binary Search in Java class BinarySearch ( int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) public static void main(String args()) ( BinarySearch ob = new BinarySearch(); int array() = ( 3, 4, 5, 6, 7, 8, 9 ); int n = array.length; int x = 4; int result = ob.binarySearch(array, x, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); ) )
 // Binary Search in C #include int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int n = sizeof(array) / sizeof(array(0)); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )
 // Binary Search in C++ #include using namespace std; int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int x = 4; int n = sizeof(array) / sizeof(array(0)); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )

Сложност на двоично търсене

Сложни времена

  • Най-добрата сложност :O(1)
  • Средна сложност на случая :O(log n)
  • Най-лошата сложност на случая :O(log n)

Сложност на пространството

Сложността на пространството на бинарното търсене е O(n).

Приложения за двоично търсене

  • В библиотеките на Java, .Net, C ++ STL
  • По време на отстраняване на грешки бинарното търсене се използва за определяне на мястото, където се случва грешката.

Интересни статии...