Problem 55285. Number of leaps in binary search
Binary search is one of the most popular searching algorithms (Binary Search Algorithm). It works only in a sorted array. It utilizes the concept of decrease and conquer. At each iteration, it halves the size of the array while searching for an element in a list of items.
While Matlab provides the 'find' or similar functions to search for an element in an array. This problem works the other way around. You have to implement the binary search algorithm here. Instead of finding the index of an element, you've to find how many jumps/iterations do you need using binary search to reach the item you are looking for.
For example,
given array, a= [2, 4, 5, 7, 8, 9, 19] and search item value= 8.
The item is located at index 5. But thats not what you are looking for.
Implementing Binary search --
- step - 1: mid_elem = 7. doesn't match and lower. so shift the search to upper half. new array is [8, 9, 19].
- step - 2: mid_elem = 9. doesn't match and higher. so, shift the search to lower half. new array is [8].
- step - 3: mid_elem=8. match.
So, no of steps =3.
If the value is not found, return -1.
Solution Stats
Problem Comments
-
1 Comment
Dyuman Joshi
on 14 Sep 2022
Test suite updated with a random input and solutions rescored.
Solution Comments
Show commentsProblem Recent Solvers7
Suggested Problems
-
Given two arrays, find the maximum overlap
1480 Solvers
-
Increment a number, given its digits
643 Solvers
-
108 Solvers
-
611 Solvers
-
704 Solvers
More from this Author165
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!