Binary Search
Description:
A binary search algorithm is a way to look for the index of a certain value in a sorted array.
The algorithm will progressively cut the original array into smaller and smaller chunks until it finds the desired value. If the desired value is not found, return -1.
Let's take a look at an illustration from Wikipedia:
The list to be searched: L = 1 3 4 6 8 9 11. The value to be found: X = 4.
Compare X to 6. X is smaller. Repeat with L = 1 3 4.
Compare X to 3. X is bigger. Repeat with L = 4.
Compare X to 4. They are equal. We're done, we found X.
This makes it efficient for particularly large arrays because it doesn't have to completely iterate over them, so it will only take logarithmic time.
Write a function binSearch that can perform a binary search on large arrays and not time out. The function will have 2 parameters, which are a sorted array and an element to search.
Note: indexOf, lastIndexOf, eval, sort and sortedIndex are disabled.
Similar Kata:
Stats:
Created | Dec 1, 2014 |
Warriors Trained | 913 |
Total Skips | 25 |
Total Code Submissions | 2277 |
Total Times Completed | 214 |
JavaScript Completions | 214 |
Total Stars | 15 |
% of votes with a positive feedback rating | 88% of 94 |
Total "Very Satisfied" Votes | 76 |
Total "Somewhat Satisfied" Votes | 14 |
Total "Not Satisfied" Votes | 4 |
Total Rank Assessments | 102 |
Average Assessed Rank | 6 kyu |
Highest Assessed Rank | 1 kyu |
Lowest Assessed Rank | 8 kyu |