Home Contact Shop Notes Questions Programming Links Dictionary Coursework FORUM Tutors
 Recommended Amazon Searches: Computer Science | Computing | Computer Systems | Database | Computing Revision

## Notes > Computation and Algorithms > Binary Search

The Binary Search algorithm searches for an item in an ordered list. The algorithm initiates by visiting the middle of the list and comparing the middle value to the desired result. If the desired result is higher than the middle value the bottom half of the list is discarded. Alternatively, if the desired value is lower than the middle value then the upper half of the list is discarded. This process is repeated until the desired result is found.

The Binary Search is a much more effective search method than a sequential or linear search, for example, especially for large sets of data. An ideal application of the Binary Search would be searching for a record in an ordered list of employees which are kept in order by the employees' unique ID. With this in mind, the Binary Search has the disadvantage of only being able to operate on an ordered set of data. Even so, there are many simple ways to order a list or set of data, and once sorted, the Binary Search can offer a very swift method of searching.

The time complexity of the Binary Search is O(log(N)) which means it is a logarithmic algorithm. This means that as the input data increases in size, the algorithm gets more efficient. This efficiency is in terms of the relationship between its average execution time and the input data size. For large sets of data (this enables successful asymptotic analysis of the algorithm), if the input list size doubles (2N), the execution time will go from a factor of log(N) to log(2N) which is a lot less than double.

Binary Search Pseudocode

```Input: ordered list and element to be searched for (the search target) Output: location of search target or 0 if target is not found Algorithm binarySearch(list[], searchTarget) last <-- length(list[]) first <-- 1 // while there are still elements to be searched through while first = last do middle <-- (first + last) / 2 // if current middle value is the search target if list[middle] = searchTarget return middle // if current middle value is less than the search target else if list[middle] < searchTarget first <-- middle + 1 // if current middle value is larger than the search target else last <-- middle - 1 end if end while // return 0 if search target not found return 0 ```

Search for "Binary Search" on: Google | Kelkoo | Amazon | eBay (UK) | eBay (US)

Search for "Binary Search" on the rest of Computing Students: Binary Search

 Home | Contact | Shop | Notes | Questions | Programming | Links | Dictionary | Coursework | Tutors Sponsored Links: Affiliate Program Articles | Computer Science Definitions | CS Degree Notes
 Copyright © 2005-2009 ComputingStudents.com This site is to be used in accordance with the ComputingStudents.com User Agreement