Binary Search is an efficient method for finding a specific value in a sorted array. This algorithm has a time complexity of O(log n) because it repeatedly divides the array in half to find the target value. In this lecture, we will cover the basic concepts of binary search, implementation methods, and practical exercises using this technique.<\/p>\n
Binary search operates according to the following procedure:<\/p>\n
This process is repeated until the target value is found.<\/p>\n
Given an integer array Print the index of the target. (An integer between 0 and n-1)<\/p>\n First, it is important to accurately understand the problem. Since we need to quickly find a specific element in a sorted array, we should use binary search.<\/p>\n Let’s implement the binary search algorithm in C++.<\/p>\n \n – The After writing the code, it is essential to run it against various test cases to ensure it returns the correct results. Consider the following tests:<\/p>\n Binary search is a very useful algorithm, especially as it exhibits excellent performance in terms of speed when working with sorted arrays. In this lecture, we understood the basic principles of binary search and implemented actual code. Mastering binary search will greatly help in solving many other algorithm problems.<\/p>\n In the next lecture, we will cover variations of binary search and various applications. I encourage you to enhance your algorithm skills through continuous learning!<\/p>\narr<\/code> and an integer target<\/code>, write a program that returns the index of target<\/code>. If target<\/code> is not found, it should return -1<\/code>.<\/p>\nInput Format<\/h3>\n
\n
n<\/code>. (1 \u2264 n \u2264 105<\/sup>)<\/li>\narr<\/code> in ascending order.<\/li>\ntarget<\/code> to be found.<\/li>\n<\/ul>\nOutput Format<\/h3>\n
Example<\/h4>\n
Input:\n 5\n 1 3 5 7 9\n 5\n\n Output:\n 2<\/code><\/pre>\nSolution Process<\/h2>\n
Step 1: Understanding the Problem<\/h3>\n
Step 2: Implementing the Binary Search Algorithm<\/h3>\n
#include <iostream>\n#include <vector>\n\nusing namespace std;\n\nint binarySearch(const vector<int> &arr, int target) {\n int left = 0;\n int right = arr.size() - 1;\n\n while (left <= right) {\n int mid = left + (right - left) \/ 2;\n\n if (arr[mid] == target) {\n return mid; \/\/ Found the target.\n } else if (arr[mid] < target) {\n left = mid + 1; \/\/ Move to the right half.\n } else {\n right = mid - 1; \/\/ Move to the left half.\n }\n }\n return -1; \/\/ Target not found.\n}\n\nint main() {\n int n;\n cout << \"Enter the size of the array: \";\n cin >> n;\n \n vector<int> arr(n);\n cout << \"Enter the elements of the array: \";\n for (int i = 0; i < n; i++) {\n cin >> arr[i];\n }\n \n int target;\n cout << \"Enter the number you want to find: \";\n cin >> target;\n\n int result = binarySearch(arr, target);\n if (result != -1) {\n cout << \"Index of the target: \" << result << endl;\n } else {\n cout << \"Target not found.\" << endl;\n }\n\n return 0;\n}<\/code><\/pre>\nStep 3: Code Explanation<\/h3>\n
binarySearch<\/code> function takes an integer vector and a target value as input and returns the index of the target value.
\n – left<\/code> and right<\/code> represent the start and end indices of the search interval.
\n – The while<\/code> loop runs while left<\/code> is less than or equal to right<\/code>.
\n – In each iteration, the central index mid<\/code> is computed, and the central element is compared with the target value to determine the next search interval.\n <\/p>\nStep 4: Testing and Verification<\/h3>\n
\n
Conclusion<\/h2>\n