{"id":1011,"date":"2023-04-21T16:47:46","date_gmt":"2023-04-21T08:47:46","guid":{"rendered":"https:\/\/www.cgdev.net\/blog\/?p=1011"},"modified":"2023-04-22T16:23:34","modified_gmt":"2023-04-22T08:23:34","slug":"binary-search","status":"publish","type":"post","link":"https:\/\/www.cgdev.net\/blog\/1011.html","title":{"rendered":"Binary Search"},"content":{"rendered":"<h3>Performance and Time Complexity<\/h3>\n<p>For any algorithm based on comparison, its worst-case time cannot be lower than O(log<sub>2<\/sub>n), so binary search is the optimal algorithm in the worst case.<\/p>\n<pre>\r\n         Found           Not found\r\nBest     O(1)             O(log<sub>2<\/sub>n)\r\nAverag   O(log<sub>2<\/sub>n)         O(log<sub>2<\/sub>n)\r\nWorst    O(log<sub>2<\/sub>n)         O(log<sub>2<\/sub>n)\r\n<\/pre>\n<p>In general there are two implementations:<\/p>\n<h3>Recursive Binary Search<\/h3>\n<pre lang='a_c'>\r\nint BinarySearch(int A[], int i, int, j, int x)\r\n{\r\n    int m = -1; \/\/ if not found, then return -1\r\n    if (i <= j)\r\n    {\r\n        m = (i + j) \/ 2;\r\n        if (A[m] < x)\r\n            m = BinarySearch(A, m + 1, j, x);\r\n        else if (x < A[m])\r\n            m = BinarySearch(A, i, m - 1, x);\r\n    }\r\n    return m;  \r\n}\r\n<\/pre>\n<h3>Iterative Binary Search<\/h3>\n<pre lang='a_c'>\r\nint BinarySearch2(int A[], int n, int x)\r\n{\r\n    int i = 0, j = n - 1, m = 0;\r\n    while (i <= j)\r\n    {\r\n        m = (i + j) \/ 2;\r\n        if (x < A[m])\r\n            j = m - 1;\r\n        else if (A[m] < x)\r\n            i = m + 1;\r\n        else\r\n            return m;\r\n    }\r\n    return -1;  \/\/not found\r\n}\r\n<\/pre>\n<h3>Binary Search in C++ STL<\/h3>\n<p>std::binary_search returns true if val in the range [first, last), else returns false. For example, we need to check 6 exists in array a:<\/p>\n<pre lang='a_c'>\r\n#include <iostream>     \r\n#include <algorithm>\r\n#include <vector>  \r\nusing namespace std;\r\n\r\nint main()\r\n{\r\n    vector<int> a = { 1, 2, 3, 4, 5, 6, 7, 8 };  \r\n    int val = 6;  \r\n    if (binary_search(arr.begin(), arr.end(), val))\r\n        cout << \"found \" << endl;\r\n    else\r\n        cout << \"not found\" << endl;\r\n\r\n    return 0;\r\n}\r\n<\/pre>\n<p>std::lower_bound returns an iterator pointing to the first element in the range [first, last) that is greater or equal to val, or last if no such element is found.<br \/>\nstd::upper_bound returns an iterator pointing to the first element in the range [first, last) that is greater than val, or last if no such element is found.<br \/>\nFor example, we check if 4 exists:<\/p>\n<pre lang='a_c'>\r\nint main() \r\n{    \r\n    vector<int> a = { 1, 2, 2, 4, 4, 4, 5, 5 };\r\n    const auto it = std::lower_bound(a.begin(), a.end(), 4);\r\n    if (it != a.end())\r\n        cout << \"found 4 at position \" << ( it - v.begin() ) << endl;\r\n    else\r\n        cout << \"not found\" << endl;\r\n\r\n    return 0;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Performance and Time Complexity For any algorithm based on comparison, its worst-case time cannot be lower than O(log2n), so binary search is the optimal algorithm in the worst case. Found Not found Best O(1) O(log2n) Averag O(log2n) O(log2n) Worst O(log2n) O(log2n) In general there are two implementations: Recursive Binary Search int BinarySearch(int A[], int i, [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[39,5],"tags":[],"class_list":["post-1011","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-cpp"],"_links":{"self":[{"href":"https:\/\/www.cgdev.net\/blog\/wp-json\/wp\/v2\/posts\/1011","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.cgdev.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.cgdev.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.cgdev.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.cgdev.net\/blog\/wp-json\/wp\/v2\/comments?post=1011"}],"version-history":[{"count":0,"href":"https:\/\/www.cgdev.net\/blog\/wp-json\/wp\/v2\/posts\/1011\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.cgdev.net\/blog\/wp-json\/wp\/v2\/media?parent=1011"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.cgdev.net\/blog\/wp-json\/wp\/v2\/categories?post=1011"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.cgdev.net\/blog\/wp-json\/wp\/v2\/tags?post=1011"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}