第二章 分支和循环(4)

【算法】二分查找

场景：搜索一个数，如果存在，返回其索引，否则返回-1

算法步骤：

1. 创建两个指针left和right。left指向数组最左边的位置序号，right指向数组最右边的位置序号。
2. 设立值middle，为(left+right)/2。
3. 把arr[middle]与我们的key进行对比。若arr[middle]大，则我们的right指针的值变为middle-1。若arr[middle]小，则我们的left指针变为middle+1
4. 将middle的值更新为(left+right)/2，再次对arr[middle]与key进行对比
5. 若arr[middle]==key，则返回middle的值。若数组中没有key，则返回-1

代码：

int binarySearch(int* nums, int key， int numsSize) {
	int left = 0;
	int right = numsSize - 1;
	while(left <= right) {
		int middle = (left + right) /2;
		int val = nums[middle];
		if(val > key)
			right = middle - 1;
		else if(val < key)
			left = middle + 1;
		else if(val == key)
			return middle;
	}
	return -1;
}

【例题】编写代码，演示多个字符从两边移动，向中间汇聚

int main() {
    char charSet1[] = "I am Arthur";
    char charSet2[] = "###########";
    int size = sizeof(charSet1) / sizeof(charSet1[0])-1;
    int left = 0;
    int right = size - 1;
    while (left <= right) {
        charSet2[left] = charSet1[left];
        charSet2[right] = charSet1[right];
        left++;
        right--;
        printf("%s\\n", charSet2);
    }
    return 0;
}

【例题】密码输入

int main() {
    char passKey[30] = "1234";
    char password[100] = { 0 };
    scanf("%s", password);
    if (strcmp(password, passKey)==0)
        printf("%s", "yes");
    return 0;
}

strcmp()函数

语法：