single
BinarySearch 1/2
メニューを表示するにはスワイプしてください
Binary search follows a 'divide and conquer' approach, when the list is divided into two halves and the element is compared with the middle element of the list. If a match is found, the location of the middle element is returned. We are goimg to implement the BS with the help of the recursion!
The main steps to implement the binary search algorithm:
-
Compare x(the desired item) with the middle element
-
If x matches with the middle element, we return the mid index
-
Else If x is greater than the mid element, then x can only lie in the right half subarray after the mid element
-
Else (x is smaller) recur for the left half
-
If none of it, the element isn't in the array
Why Binary search?
Study the table to understand why BS is better than the Linear Search!
Binary search works only if elements of the array are arranged in sorted order.
| Linear search | Binary Search |
|---|---|
| The linear search starts searching from the first element and compares each element with a searched element till the element is not found | It finds the position of the searched element by finding the middle element of the array |
| The worst-case scenario for finding the element is O(n) | The worst-case scenario for finding the element is O(log2n)(beter!) |
| It is preferrable for the small-sized data sets | It is preferrable for the large-size data sets(better!) |
Now we will try to implement the BS algorithm! Use hints if needed! Be careful with the tabulation!
スワイプしてコーディングを開始
- Set condition if the
rightis greater than theleft. - Set the
middlevarible. Themiddleequals theleft + (right - left) // 2. - Set condition if the element in the middle equals the
x. - Perform recursion with the left part of the array if the
xis greater than the middle element. - Perform recursion with the right part of the array if the
xis lower than the middle element.
解答
実践的な練習のためにデスクトップに切り替える下記のオプションのいずれかを利用して、現在の場所から続行するフィードバックありがとうございます！
single
AIに質問する
AIに質問する
何でも質問するか、提案された質問の1つを試してチャットを始めてください
