二分查找 Binary Search

Given a sorted array arr[] of n elements, write a function to search a given element x in arr[].

给定一个由n个元素组成的有序数组arr[]，在arr[]中编写一个函数来搜索给定的元素x。

A simple approach is to do linear search.The time complexity of above algorithm is O(n). Another approach to perform the same task is using Binary Search.

一个简单的方法是做线性搜索。上述算法的时间复杂度为O(n)。执行相同任务的另一种方法是使用二分查找。

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.

通过将搜索间隔重复分成两半来搜索已排序的数组。从覆盖整个数组的区间开始。如果搜索键的值小于区间中间的项，则将区间缩小到下半部分。否则就缩小到上半部分。重复检查，直到找到值或间隔为空。

Example :

二分查找 Binary Search

The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Log n).

// Java implementation of recursive Binary Search 
class BinarySearch { 
	// Returns index of x if it is present in arr[l.. 
	// r], else return -1 
	int binarySearch(int arr[], int l, int r, int x) 
	{ 
		if (r >= l) { 
			int mid = l + (r - l) / 2; //l ， r 为left ,right 

			// If the element is present at the 
			// middle itself 
			if (arr[mid] == x) 
				return mid; 

			// If element is smaller than mid, then 
			// it can only be present in left subarray 
			if (arr[mid] > x) 
				return binarySearch(arr, l, mid - 1, x); 

			// Else the element can only be present 
			// in right subarray 
			return binarySearch(arr, mid + 1, r, x); 
		} 

		// We reach here when element is not present 
		// in array 
		return -1; 
	} 

	// Driver method to test above 
	public static void main(String args[]) 
	{ 
		BinarySearch ob = new BinarySearch(); 
		int arr[] = { 2, 3, 4, 10, 40 }; 
		int n = arr.length; 
		int x = 10; 
		int result = ob.binarySearch(arr, 0, n - 1, x); 
		if (result == -1) 
			System.out.println("Element not present"); 
		else
			System.out.println("Element found at index " + result); 
	} 
} 
/* This code is contributed by Rajat Mishra */

二分查找 Binary Search

相关推荐