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

Order of efficiency - linear search, Linear search employee an exhaustive m...

Linear search employee an exhaustive method of verified each element in the array against a key value. Whereas a match is found, the search halts. Will sorting the array before uti

What is algorithms optimality, What is algorithm's Optimality? Optimali...

What is algorithm's Optimality? Optimality  is  about  the  complexity  of  the  problem  that  algorithm  solves.  What  is  the  minimum amount  of  effort  any  algorithm  w

Hw7, Handout 15 COMP 264: Introduction to Computer Systems (Section 001) Sp...

Handout 15 COMP 264: Introduction to Computer Systems (Section 001) Spring 2013 R. I. Greenberg Computer Science Department Loyola University Water TowerCampus, Lewis Towers 524 82

Example which cause problems for hidden-surface algorithms, Example which c...

Example which cause problems for some hidden-surface algorithms Some special cases, which cause problems for some hidden-surface algorithms, are penetrating faces and cyclic ov

Data manipulation, perform the following length operation LENGTH("welcome t...

perform the following length operation LENGTH("welcome to ICA")=

Graph terminologies, Graph terminologies : Adjacent vertices: Two vert...

Graph terminologies : Adjacent vertices: Two vertices a & b are said to be adjacent if there is an edge connecting a & b. For instance, in given Figure, vertices 5 & 4 are adj

Find the optimal solution - branch and bound algorithm, Consider the follow...

Consider the following 5-city traveling salesman problem. The distance between each city (in miles) is shown in the following table: (a) Formulate an IP whose solution will

Avl tree rotations, AVL trees and the nodes it contains must meet strict ba...

AVL trees and the nodes it contains must meet strict balance requirements to maintain O(log n) search time. These balance restrictions are kept maintained via various rotation func

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