Searching Arrays
Tags: java, programming, learning, beginners
Published: 2024-05-28 14:31:19

If an array is sorted, binary search is more efficient than linear search for finding an element in the array. _Searching_ is the process of looking for a specific element in an array—for example, discovering whether a certain score is included in a list of scores. Searching is a common task in computer programming. Many algorithms and data structures are devoted to searching. This section discusses two commonly used approaches, _linear search_ and _binary search_.

## The Linear Search Approach

The linear search approach compares the **key** element key sequentially with each element in the array. It continues to do so until the key matches an element in the array or the array is exhausted without a match being found. If a match is made, the linear search returns the index of the element in the array that matches the key. If no match is found, the search returns **-1**. The **linearSearch** method in the program below gives the solution.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/j78bsuanqz2cjmvwz5ij.png)

The linear search method compares the key with each element in the array. The elements can be in any order. On average, the algorithm will have to examine half of the elements in an array before finding the key, if it exists. Since the execution time of a linear search increases linearly as the number of array elements increases, linear search is inefficient for a large array.

## The Binary Search Approach

Binary search is the other common search approach for a list of values. For binary search to work, the elements in the array must already be ordered. Assume that the array is in ascending order. The binary search first compares the key with the element in the middle of the array. Consider the following three cases:

- If the key is less than the middle element, you need to continue to search for the key only in the first half of the array.
- If the key is equal to the middle element, the search ends with a match.
- If the key is greater than the middle element, you need to continue to search for the key only in the second half of the array.

Clearly, the binary search method eliminates at least half of the array after each comparison. Sometimes you eliminate half of the elements, and sometimes you eliminate half plus one. Suppose that the array has _n_ elements. For convenience, let **n** be a power of **2**. After the first comparison, **n/2** elements are left for further search; after the second comparison, **(n/2)/2** elements are left. After the **k**th comparison, **n/2^k** elements are left for further search. When **k = log2n**, only one element is left in the array, and you need only one more comparison. Therefore, in the worst case when using the binary search approach, you need **log2n+1** comparisons to find an element in the sorted array. In the worst case for a list of **1024** (2^10) elements, binary search requires only **11** comparisons, whereas a linear search requires **1023** comparisons in the worst case.

The portion of the array being searched shrinks by half after each comparison. Let **low** and **high** denote, respectively, the first index and last index of the array that is currently being searched. Initially, **low** is **0** and **high** is **list.length–1**. Let **mid** denote the index of the middle element, so **mid** is **(low + high)/2**. Below shows how to find key **11** in the list {**2**, **4**, **7**, **10**, **11**, **45**, **50**, **59**, **60**, **66**, **69**, **70**, **79**} using binary search.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xrhkomxbakokir7nwb5l.png)

You now know how the binary search works. The next task is to implement it in Java. Don’t rush to give a complete implementation. Implement it incrementally, one step at a time. You may start with the first iteration of the search, as shown below a. It compares the key with the middle element in the list whose **low** index is **0** and **high** index is **list.length - 1**. If **key < list[mid]**, set the **high** index to **mid - 1**; if **key == list[mid]**, a match is found and return **mid**; if **key > list[mid]**, set the **low** index to **mid + 1**.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1eguzauv4t0kar2jdkts.png)

Next consider implementing the method to perform the search repeatedly by adding a loop, as shown in above b. The search ends if the key is found, or if the key is not found when **low > high**.

When the key is not found, **low** is the insertion point where a key would be inserted to maintain the order of the list. It is more useful to return the insertion point than **-1**. The method must return a negative value to indicate that the key is not in the list. Can it simply return **–low**? No. If the key is less than **list[0]**, **low** would be **0**. **-0** is **0**. This would indicate that the key matches **list[0]**. A good choice is to let the method return **–low – 1** if the key is not in the list. Returning **–low – 1** indicates not only that the key is not in the list, but also where the key would be inserted.

The complete program is given below:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8fdhs4lzion66b9mtgs6.png)

The binary search returns the index of the search key if it is contained in the list (line 25). Otherwise, it returns **–low – 1** (line 30).

What would happen if we replaced **(high >= low)** in line 20 with (**high > low**)? The search would miss a possible matching element. Consider a list with just one element. The search would miss the element.

Does the method still work if there are duplicate elements in the list? Yes, as long as the elements are sorted in increasing order. The method returns the index of one of the matching elements if the element is in the list.

Here is the table that lists the low and high values when the method exits and the value returned from invoking the method.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/m5yzehfwn5s9bdq6139s.png)

Linear search is useful for finding an element in a small array or an unsorted array, but it is inefficient for large arrays. Binary search is more efficient, but it requires that the array be presorted.