Binary search algorithm
Binary Search Algorithm[edit | edit source]
The binary search algorithm is a fundamental algorithm in computer science used to efficiently find a target value within a sorted array. It operates by repeatedly dividing the search interval in half, comparing the target value to the middle element of the array, and narrowing the search to the half where the target must lie. This process continues until the target value is found or the search interval is empty.
Algorithm Description[edit | edit source]
The binary search algorithm works on the principle of divide and conquer. It requires that the array is sorted beforehand. The steps of the algorithm are as follows:
Initialize two pointers, `low` and `high`, to the beginning and end of the array, respectively. While `low` is less than or equal to `high`, repeat the following steps:
- Calculate the middle index, `mid`, as the integer division of `(low + high) / 2`.
- Compare the target value to the element at the `mid` index.
- If the target value is equal to the element at `mid`, return `mid` as the index of the target.
- If the target value is less than the element at `mid`, set `high` to `mid - 1`.
- If the target value is greater than the element at `mid`, set `low` to `mid + 1`.
If the loop ends without finding the target, return an indication that the target is not present in the array.
Time Complexity[edit | edit source]
The time complexity of the binary search algorithm is O(log n), where n is the number of elements in the array. This logarithmic time complexity arises because the algorithm halves the search space with each iteration.
Applications[edit | edit source]
Binary search is widely used in various applications, including:
- Searching in databases and large datasets.
- Implementing efficient data structures like binary search trees.
- Solving problems in competitive programming and coding interviews.
Limitations[edit | edit source]
Binary search requires that the array be sorted prior to searching. If the array is not sorted, the algorithm will not function correctly. Additionally, binary search is not suitable for linked lists or other data structures where random access is not possible.
Also see[edit | edit source]
Search WikiMD
Ad.Tired of being Overweight? Try W8MD's physician weight loss program.
Semaglutide (Ozempic / Wegovy and Tirzepatide (Mounjaro / Zepbound) available.
Advertise on WikiMD
|
WikiMD's Wellness Encyclopedia |
| Let Food Be Thy Medicine Medicine Thy Food - Hippocrates |
Translate this page: - East Asian
中文,
日本,
한국어,
South Asian
हिन्दी,
தமிழ்,
తెలుగు,
Urdu,
ಕನ್ನಡ,
Southeast Asian
Indonesian,
Vietnamese,
Thai,
မြန်မာဘာသာ,
বাংলা
European
español,
Deutsch,
français,
Greek,
português do Brasil,
polski,
română,
русский,
Nederlands,
norsk,
svenska,
suomi,
Italian
Middle Eastern & African
عربى,
Turkish,
Persian,
Hebrew,
Afrikaans,
isiZulu,
Kiswahili,
Other
Bulgarian,
Hungarian,
Czech,
Swedish,
മലയാളം,
मराठी,
ਪੰਜਾਬੀ,
ગુજરાતી,
Portuguese,
Ukrainian
Medical Disclaimer: WikiMD is not a substitute for professional medical advice. The information on WikiMD is provided as an information resource only, may be incorrect, outdated or misleading, and is not to be used or relied on for any diagnostic or treatment purposes. Please consult your health care provider before making any healthcare decisions or for guidance about a specific medical condition. WikiMD expressly disclaims responsibility, and shall have no liability, for any damages, loss, injury, or liability whatsoever suffered as a result of your reliance on the information contained in this site. By visiting this site you agree to the foregoing terms and conditions, which may from time to time be changed or supplemented by WikiMD. If you do not agree to the foregoing terms and conditions, you should not enter or use this site. See full disclaimer.
Credits:Most images are courtesy of Wikimedia commons, and templates Wikipedia, licensed under CC BY SA or similar.
Contributors: Prab R. Tumpati, MD
