0

Guys i need to know about binary search of a value, concept clearly... I seen programs but it confusing me

Help me to resolve

7th Feb 2017, 6:50 AM
tharun
tharun - avatar
1 Antwort
0
When we are given an array, and tasked to look for something (a key) in the array, the most direct method is to conduct a linear search through the list. However, this is going to be super slow (surprise!), so binary search is much faster way to look for the key. So, what is binary search? Essentially, binary search is an algorithm which reduces the size of the array to be searched by half in each iteration (run). Note that binary search can only be used in an already sorted array. So how does it search in a sorted array? Imagine you keep track of 2 variables, int start and int end. To begin searching, you go to int mid, which is (start + end) / 2. If whatever is in the middle of the array is larger than the key, then you repeat the search in the lower half of the array (change the value of end to mid - 1). Since the array is sorted, you know where to continue your search! Conversely, if it is smaller than the key, then you repeat the search in the upper half of the array (change begin to mid + 1). In short, you can see binary search as such: 1. find middle element 2. compare with key 2a. if middle element > key, repeat steps 1 to 2 in the lower half of the array 2b. else if middle element < key, repeat steps 1 to 2 in upper half of the array
8th Feb 2017, 6:39 PM
Joanne Ong