Binary Search

Introduction

Binary Search is an efficient algorithm for finding an item from a sorted list of items. A simple approach is to do a linear search. The time complexity of the linear search algorithm is O(n). Binary Search works in the following manner:

• Search a sorted array by repeatedly dividing the search interval in half.
• Begin with an interval covering the whole array.
• If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half.
• Otherwise, narrow it to the upper half.
• Repeatedly check until the value is found or the interval is empty.