Searching in Arrays: Linear and Binary Search

Hello students, welcome to Kwickprep. A list has one thousand roll numbers. Checking one by one could take a thousand steps. Can you find any roll number in just ten steps? Yes, if the list is sorted. Today we learn linear search, binary search, and the exam programs for both.

Searching means finding whether a value is present in an array. The value we are looking for is called the search key. If the key is found, we report its index, which is its position. If it is not found, we report minus one, or print a message. Today we learn two methods, linear search and binary search.

Our array is fifteen, forty two, eight, twenty three and four, and the key is twenty three. The pointer starts at index zero. Fifteen is not twenty three, so it moves on. At index one, forty two is not a match either. At index two, eight is not a match. At index three, twenty three matches, so the search stops and reports index three.

Here is the same search in Java. N is the array, K is the key, and pos is the position, which starts at minus one. The loop checks every element from the first index. When an element equals the key, we store its index in pos. Break stops the loop at once, because there is no need to look further. So it prints three. If the key were fifty, pos would stay minus one.

Let us note four facts about linear search. It works on any array, whether sorted or not. It simply checks the elements one by one from the start. In the best case, the key is the very first element, so one comparison is enough. In the worst case, the key is last or missing, so every element is checked.

Binary search works like opening a dictionary near the middle. First, the array must already be sorted, in ascending order. We look at the middle element and compare it with the key. If the key is smaller, it can only be in the left half, so we throw away the right half. If the key is bigger, we throw away the left half. We repeat this until the key is found, or no elements are left.

Our sorted array is four, eight, fifteen, twenty three, forty two, fifty six and seventy one. The key is seventy one. Low is zero and high is six, so mid is three, and the value there is twenty three. Seventy one is bigger, so low becomes four. Now mid is five, with fifty six. Seventy one is still bigger, so low becomes six. Now mid is six, the value is seventy one, and the key is found at index six.

Here is the heart of the binary search program. Lo and hi, short for low and high, mark the two ends of the range, and P, the position, starts at minus one. The loop runs while the range is not empty and the key is not yet found. M is the middle index, found by adding lo and hi and dividing by two. If the middle value equals the key, P records that index. If the middle value is smaller than the key, lo moves to M plus one. Otherwise hi moves to M minus one. For our array and key seventy one, P ends as six.

Pause and predict. What happens if we search the same array for thirty? Mid is three, with twenty three. Thirty is bigger, so low becomes four. Mid is five, with fifty six. Thirty is smaller, so high becomes four. Mid is four, with forty two. Thirty is smaller, so high becomes three. Now low is more than high, so the range is empty. P stays minus one, which means not found.

Now let us compare the two searches. Linear search works on any array, but binary search needs a sorted array. Linear search checks one by one, while binary search halves the range every step. For one thousand items, linear search may need one thousand checks, but binary search needs only about ten. So linear search suits small or unsorted lists, and binary search suits large sorted lists.

Board exams also ask you to search for a name. C holds three city names, and K is the key, Pune. The only change from a number search is how we compare. Strings must be compared with equals, not double equals. Pune is at index one, so it prints one.

Board questions usually follow a fixed pattern. First, input ten numbers into an array, and then input the key to search. The question tells you which search to use, and binary search needs sorted data. If found, print Search successful along with the position. If not, print Search unsuccessful. If the question asks for position counted from one, print the index plus one.

Some exams ask for linear search in pseudocode. Found starts as false, and index starts at zero. The loop runs while the key is not found and fewer than ten elements are checked. Each time, index moves on by one, so it goes from one to ten. If that element matches the key, found becomes true, and the loop stops.

Let us revise. Linear search checks elements one by one, and it works on any array. Binary search halves the range each time, but the array must be sorted. The middle index is low plus high, divided by two. When low goes past high, the key is not there, so report minus one. And when you search names, compare them with equals.