Problem 55285. Number of leaps in binary search

Created by Asif Newaz

Solve Later

{"parts":[{"partUri":"/matlab/document.xml","contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?><w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Binary search is one of the most popular searching algorithms (</w:t></w:r><w:hyperlink w:docLocation=\"https://en.wikipedia.org/wiki/Binary_search_algorithm\"><w:r><w:t>Binary Search Algorithm</w:t></w:r></w:hyperlink><w:r><w:t>). 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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>For example, </w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>given array, a= [2, 4,  5, 7, 8, 9, 19] and search item value= 8.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>The item is located at index 5. But thats not what you are looking for.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Implementing Binary search --</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>step - 1: mid_elem = 7. doesn't match and lower. so shift the search to upper half. new array is [8, 9, 19].</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>step - 2: mid_elem = 9. doesn't match and higher. so, shift the search to lower half. new array is [8].</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>step - 3: mid_elem=8. match.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>So, no of steps =3.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>If the value is not found, return -1.</w:t></w:r></w:p></w:body></w:document>","relationship":null}],"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","target":"/matlab/document.xml","relationshipId":"rId1"}]}

<div style = "text-align: start; line-height: 20.4333px; min-height: 0px; white-space: normal; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, monospace; font-style: normal; font-size: 14px; font-weight: 400; text-decoration: rgb(0, 0, 0); white-space: normal; "><div style="block-size: 457.3px; display: block; min-width: 0px; padding-block-start: 0px; padding-top: 0px; perspective-origin: 407px 228.65px; transform-origin: 407px 228.65px; vertical-align: baseline; "><div style="block-size: 63px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 31.5px; text-align: left; transform-origin: 384px 31.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 199.5px 8px; transform-origin: 199.5px 8px; unicode-bidi: normal; "><span style="">Binary search is one of the most popular searching algorithms (</span></span><a target='_blank' href = "https://en.wikipedia.org/wiki/Binary_search_algorithm"><span style=""><span style="">Binary Search Algorithm</span></span></a><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 108px 8px; transform-origin: 108px 8px; unicode-bidi: normal; "><span style="">). 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.</span></span></div><div style="block-size: 63px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 31.5px; text-align: left; transform-origin: 384px 31.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 384px 8px; transform-origin: 384px 8px; unicode-bidi: normal; "><span style="">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.</span></span></div><div style="block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 10.5px; text-align: left; transform-origin: 384px 10.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 8px; transform-origin: 0px 8px; unicode-bidi: normal; "><span style=""></span></span></div><div style="block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 10.5px; text-align: left; transform-origin: 384px 10.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 43px 8px; transform-origin: 43px 8px; unicode-bidi: normal; "><span style="">For example, </span></span></div><div style="block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 10.5px; text-align: left; transform-origin: 384px 10.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 194.5px 8px; transform-origin: 194.5px 8px; unicode-bidi: normal; "><span style="">given array, a= [2, 4,  5, 7, 8, 9, 19] and search item value= 8.</span></span></div><div style="block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 10.5px; text-align: left; transform-origin: 384px 10.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 215px 8px; transform-origin: 215px 8px; unicode-bidi: normal; "><span style="">The item is located at index 5. But thats not what you are looking for.</span></span></div><div style="block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 10.5px; text-align: left; transform-origin: 384px 10.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 94px 8px; transform-origin: 94px 8px; unicode-bidi: normal; "><span style="">Implementing Binary search --</span></span></div><ol style="block-size: 61.3px; counter-reset: list-item 0; font-family: Helvetica, Arial, sans-serif; list-style-type: decimal; margin-block-end: 20px; margin-block-start: 10px; margin-bottom: 20px; margin-top: 10px; perspective-origin: 391px 30.65px; transform-origin: 391px 30.65px; margin-top: 10px; margin-bottom: 20px; "><li style="block-size: 20.4333px; counter-reset: none; display: list-item; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-start: 56px; margin-left: 56px; margin-top: 0px; perspective-origin: 363px 10.2167px; text-align: left; transform-origin: 363px 10.2167px; white-space: pre-wrap; margin-left: 56px; "><span style="block-size: auto; display: inline; margin-inline-start: 0px; margin-left: 0px; perspective-origin: 328px 8px; transform-origin: 328px 8px; unicode-bidi: normal; "><span style="">step - 1: mid_elem = 7. doesn't match and lower. so shift the search to upper half. new array is [8, 9, 19].</span></span></li><li style="block-size: 20.4333px; counter-reset: none; display: list-item; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-start: 56px; margin-left: 56px; margin-top: 0px; perspective-origin: 363px 10.2167px; text-align: left; transform-origin: 363px 10.2167px; white-space: pre-wrap; margin-left: 56px; "><span style="block-size: auto; display: inline; margin-inline-start: 0px; margin-left: 0px; perspective-origin: 311.5px 8px; transform-origin: 311.5px 8px; unicode-bidi: normal; "><span style="">step - 2: mid_elem = 9. doesn't match and higher. so, shift the search to lower half. new array is [8].</span></span></li><li style="block-size: 20.4333px; counter-reset: none; display: list-item; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-start: 56px; margin-left: 56px; margin-top: 0px; perspective-origin: 363px 10.2167px; text-align: left; transform-origin: 363px 10.2167px; white-space: pre-wrap; margin-left: 56px; "><span style="block-size: auto; display: inline; margin-inline-start: 0px; margin-left: 0px; perspective-origin: 91px 8px; transform-origin: 91px 8px; unicode-bidi: normal; "><span style="">step - 3: mid_elem=8. match.</span></span></li></ol><div style="block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 10.5px; text-align: left; transform-origin: 384px 10.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 59.5px 8px; transform-origin: 59.5px 8px; unicode-bidi: normal; "><span style="">So, no of steps =3.</span></span></div><div style="block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 10.5px; text-align: left; transform-origin: 384px 10.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 0px 8px; transform-origin: 0px 8px; unicode-bidi: normal; "><span style=""></span></span></div><div style="block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 10.5px; text-align: left; transform-origin: 384px 10.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 107px 8px; transform-origin: 107px 8px; unicode-bidi: normal; "><span style="">If the value is not found, return -1.</span></span></div></div></div>

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.

Solve

Solution Stats

13 Solutions
6 Solvers

Last Solution submitted on Apr 09, 2023

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Dyuman Joshi on 14 Sep 2022

Test suite updated with a random input and solutions rescored.

Solution Comments

Show comments

Problem Recent Solvers6

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 55285. Number of leaps in binary search

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers6

Suggested Problems

More from this Author165

Problem Tags

Community Treasure Hunt

Problem 55285. Number of leaps in binary search

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers6

Suggested Problems

More from this Author165

Problem Tags

Community Treasure Hunt

Players