Tag Archives: Binary Search

Binary Search Algorithm, written in C [with video example step-to-step]

In computer science, a binary search is an algorithm for locating the position of an item in a sorted array.[1][2] Binary search works by comparing an input value to the middle element of the array. The comparison determines whether the element is equal to the input, less than the input or greater. When the element being compared to equals the input the search stops and typically returns the position of the element. If the element is not equal to the input then a comparison is made to determine whether the input is less than or greater than the element. Depending on which it is the algorithm then starts over but only searching the top or bottom subset of the array’s elements. If the input is not located within the array the algorithm will usually output a unique value indicating this. This method halves the number of items to check each time, so it finds it or determines it’s not present in logarithmic time. A binary search is a dichotomic divide and conquer search algorithm.
It is useful to find where an item is in a sorted array. For example, if you had an array for contact information, with people’s names, addresses, and telephone numbers sorted by name, you could use binary search to find out a few useful facts: whether the person’s information is in the array, what the person’s address is, and what the person’s telephone number is.
Continue reading Binary Search Algorithm, written in C [with video example step-to-step]