Бинарна претрага

У овом упутству ћете научити како функционише бинарно претраживање. Такође, наћи ћете и радне примере бинарне претраге на Ц, Ц ++, Јава и Питхон.

Бинарно претраживање је алгоритам претраживања за проналажење положаја елемента у сортираном низу.

У овом приступу, елемент се увек претражује усред дела низа.

Бинарна претрага се може применити само на разврстаној листи ставки. Ако елементи већ нису сортирани, прво их морамо сортирати.

Бинарна претрага ради

Бинарни алгоритам претраживања може се применити на два начина о којима се говори у наставку.

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

Рекурзивна метода следи приступ подели и освоји.

У наставку се разматрају општи кораци за обе методе.

  1. Низ у којем ће се вршити претрага је: Иницијални низ
    Нека x = 4буде елемент за претрагу .
  2. Поставите два показивача ниско и високо на најнижој и највишој позицији. Постављање показивача
  3. Пронађите средњи елемент у средини низа, тј. (arr(low + high)) / 2 = 6. Средњи елемент
  4. Ако је к == мид, а затим вратите мид.Елсе, упоредите елемент који желите претражити са м.
  5. Ако x> mid, упоредите к са средњим елементом елемената на десној страни средине. То се постиже постављањем ниског на low = mid + 1.
  6. Иначе, упоредите к са средњим елементом елемената на левој страни средине. То се постиже постављањем високо на high = mid - 1. Проналажење средњег елемента
  7. Поновите кораке 3 до 6 док ниска не достигне високу. Средњи елемент
  8. x = 4се налази. Нашао

Бинарни алгоритам претраживања

Метода понављања

ради док се показивачи ниско и високо не сретну. мид = (лов + хигх) / 2 иф (к == арр (мид)) ретурн мид елсе иф (к> А (мид)) // к је на десној страни лов = мид + 1 елсе // к је укључен лева страна високо = средина - 1

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

 бинариСеарцх (арр, к, лов, хигх) иф лов> хигх ретурн Фалсе елсе мид = (лов + хигх) / 2 иф к == арр (мид) ретурн мид елсе иф к <дата (мид) // к ис он десна страна враћа бинариСеарцх (арр, к, мид + 1, хигх) елсе // к је на десној страни ретурн бинариСеарцх (арр, к, лов, мид - 1)

Примери Питхон-а, Јава-е, Ц / Ц ++ (итеративни метод)

Питхон Јава Ц Ц ++ 
 # 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); )

Примери Питхон-а, Јава-е, Ц / Ц ++ (рекурзивна метода)

Питхон Јава Ц Ц ++ 
 # 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).

Бинарне апликације за претрагу

  • У библиотекама Јава, .Нет, Ц ++ СТЛ
  • Током отклањања грешака, бинарна претрага се користи за одређивање места на којем се грешка дешава.

Занимљиви Чланци...