Binary search, Data Structure & Algorithms

Assignment Help:

An unsorted array is searched through linear search that scans the array elements one by one until the wanted element is found.

The cause for sorting an array is that we search the array "quickly". Now, if the array is sorted, we can use binary search, which greatly halves the size of the search space each time it study one array element.

An array-based binary search chooses the middle element in the array & compares its value to that of the key value. Since, the array is sorted; if the key value is less than the middle value then the key has to be in the first half of the array. Similarly, if the value of the key item is greater than that of the middle value within the array, then it is known that the key lies into second half of the array. In either case, in reality we can, "throw out" one half of search space or array along with only one comparison.

Now, knowing that the key has to be in one half of the array or the other, the binary search study the mid value of the half wherein the key has to reside. Thus, the algorithm narrows the search area by half at each step till it has either found the key data or the search fails.

As the name recommend, binary means two, so it split an array into two halves for searching. This search is applicable only onto an ordered table (in either ascending or in descending order).

Let us write down an algorithm for Binary Search & then we will discuss it. The array contains elements stored in ascending order.


Related Discussions:- Binary search

Indexed sequential files, Indexed Sequential Files An index is inserted...

Indexed Sequential Files An index is inserted to the sequential file to provide random access. An overflow area required to be maintained to permit insertion in sequence. I

Sorting, explain quick sort algorithm

explain quick sort algorithm

Simplifying assumptions of wire frame representation, Simplifying Assumptio...

Simplifying Assumptions of wire frame representation Neglect colour - consider Intensity: For now we shall forget about colour and restrict our discussion just to the intensi

What is a linear array, What is a linear array? An array is a way to re...

What is a linear array? An array is a way to reference a series of memory locations using the similar name. Every memory location is shown by an array element. An  array elemen

Explain binary search tree, Binary search tree. A binary search tree is...

Binary search tree. A binary search tree is a binary tree that is either empty or in which every node having a key that satisfies the following conditions: - All keys (if an

Linked list, create aset of ten numbers.then you must divide it into two s...

create aset of ten numbers.then you must divide it into two sets numbers which are set of odd numbers and set of even numbers.

Explain principle of optimality, Explain principle of Optimality It ind...

Explain principle of Optimality It indicates that an optimal solution to any instance of an optimization problem is composed of  optimal solutions to its subinstances.

Explain first - fit method, First - Fit Method: -    The free list is trave...

First - Fit Method: -    The free list is traversed sequentially to search the 1st free block whose size is larger than or equal to the amount requested. Once the block is found it

Applications of binary trees, In computer programming, Trees are utilized ...

In computer programming, Trees are utilized enormously. These can be utilized for developing database search times (binary search trees, AVL trees, 2-3 trees, red-black trees), Gam

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd